491-递增子序列.md

491-递增子序列

原题

给你一个整数数组 nums ，找出并返回所有该数组中不同的递增子序列，递增子序列中 至少有两个元素 。你可以按 任意顺序 返回答案。 数组中可能含有重复元素，如出现两个整数相等，也可以视作递增序列的一种特殊情况。

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

输入：nums = [4,4,3,2,1] 输出：[[4,4]]

首先第一种方法就是使用暴力循环

使用深度递归的方式

const findSubsequences = function (nums) {
  const res = [];
  const len = nums.length;
  const set = new Set();

  const dfs = (start, path) => {
    // 添加进结果集，基本上的回溯法或者深度遍历，都会有这个
    // 就是边界的判断，判断成功了就加入结果集
    if (path.length >= 2) {
      const str = path.toString();
      // 用 set 来进行一次判重，只要不是重复的就可以添加进去
      if (!set.has(str)) {
        res.push(path.slice());
        set.add(str);
      }
    }

    for (let i = start; i < len; i++) {
      const prev = path[path.length - 1];
      const cur = nums[i];

      // 因为只是求上升子序列，而不是必须是连续的
      if (path.length === 0 || prev <= cur) {
        path.push(cur);
        dfs(i + 1, path);
        path.pop();
      }
    }
  };

  dfs(0, []);
  return res;
};

let result = findSubsequences([1, 3, 4, 7, 7]);
console.log(result);

还有一种方法，但是我没有理解透，看作者的文字到时知道他在说什么，但是写出代码来的时候，还是判定的条件还是没大懂 来自

const findSubsequences = (nums) => {
  const res = [];
  const len = nums.length;

  const dfs = (start, path) => {
    if (start === len) {
      if (path.length >= 2) {
        res.push(path.slice());
        return;
      }
    }

    path.push(nums[start]);
    for (let i = start + 1; i <= len; i++) {
      const prev = nums[start];
      const cur = nums[i];
      // 这里的 if 条件和下面的 else if 条件是做了什么，又是为什么要这么做？
      if (i < len && cur === prev) {
        dfs(i, path);
        break;
      } else if (i === len || prev < cur) {
        dfs(i, path);
      }
    }

    path.pop();
  };

  for (let i = 0; i < len; i++) {
    dfs(i, []);
  }

  return res;
};