递增子序列

题目

题目来源：力扣（LeetCode）

给定一个整型数组, 你的任务是找到所有该数组的递增子序列，递增子序列的长度至少是 2 。

示例：

输入：[4, 6, 7, 7]
输出：[[4, 6], [4, 7], [4, 6, 7], [4, 6, 7, 7], [6, 7], [6, 7, 7], [7,7], [4,7,7]]

思路分析

一个递增子序列 path 怎么产生？它的元素是从 nums 中一个个选的。比如 [4,2,7,7]，path 选第一个数，有 4 种选择：从 nums[0] 到 nums[3]。
选了nums[i]之后，会在 nums[i+1] 到末尾的数中，再选下一个……
以此类推，直到没得选为止。当 path 满足要求，就可以加入解集，这是递归回溯的思路。

1. 在从下标 start 到末尾的子数组中选合适的数推入 path，path 也作为参数，在递归过程中，不断选 数字入 path。
2. 通过 for 循环枚举出当前的所有选择——（展开不同的递归分支）。选择了一个数，推入 path，往 下继续选择，继续递归。
3. 当 start 指针到达边界，所有数字都组成序列，结束递归。基于当前选择的递归，已经考察了所有可 能，这时会回溯，path 要撤销最末尾的数字，切入别的分支。
4. 我们用一个 set 存储每个合格的 path，下次遇到重复的，不让它加入解集即可。

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
const findSubsequences = (nums) => {
  const result = [];
  const length = nums.length;
  const set = new Set();
  const dfs = (start, path) => {
    if (path.length >= 2) {
      const str = path.toString(); // path数组 转成字符串
      if (!set.has(str)) {         // set中没有存有当前path
        result.push(path.slice());    // 推入一份path的拷贝
        set.add(str);              // 存入set，记录一下
      }
    }
    for (let i = start; i < length; i++) {      // 枚举出当前所有的选项，从start到末尾
      const prev = path[path.length - 1];    // 上一个选择，即path数组的末尾元素
      const curr = nums[i];                   // 当前选择
      if (path.length == 0 || prev <= curr) { // 如果path为空，或满足递增关系，则可选择
        path.push(curr);                      // 选择当前的数字
        dfs(i + 1, path);                    // 继续往下递归，注意传的是i+1
        path.pop();                          // 撤销选择当前数字，选择别的数字
      }
    }
  };
  dfs(0, []); //递归的入口，从下标0到末尾的数组中选择合适的数加入path，组成解集。初始path是空数组
  return result;
};