491.非递减子序列

链接：491.非递减子序列
难度：Medium
标签：位运算、数组、哈希表、回溯
简介：给定一个整型数组, 你的任务是找到所有该数组的递增子序列，递增子序列的长度至少是 2。

题解 1 - typescript

• 编辑时间：2020-08-25
• 执行用时：292ms
• 内存消耗：55.9MB
• 编程语言：typescript
• 解法介绍：深度遍历每种可能,剪纸+回溯

function findSubsequences(nums: number[]): number[][] {
  const len = nums.length;
  if (len === 0) return [];
  const arr: number[][] = [];
  const arrSet = new Set<string>();
  findNext();
  return arr.filter(v => v.length !== 1);
  function findNext(now: number[] = [], i = 0): void {
    for (; i < len; i++) {
      const num = nums[i];
      if (now[now.length - 1] > num) continue;
      now.push(num);
      const clone = [...now];
      const cloneSetStr = clone.join(',');
      if (!arrSet.has(cloneSetStr)) {
        arr.push(clone);
        arrSet.add(cloneSetStr);
      }
      findNext(now, i + 1);
      now.pop();
    }
  }
}