10. 递增子序列（491）

一、题目内容 中等

给你一个整数数组 nums ，找出并返回所有该数组中不同的递增子序列，递增子序列中 至少有两个元素 。
你可以按 任意顺序 返回答案。

数组中可能含有重复元素，如出现两个整数相等，也可以视作递增序列的一种特殊情况。

示例1：

输入：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]]

示例2：

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

提示：

• 1 <= nums.length <= 15
• -100 <= nums[i] <= 100

  二、解题思路

  这一道题，要求在原来的数组顺序中，找出递增的子序列。这就卡死了我们去排序数组的想法。

那我们还是需要解决，去重的问题：分为不同支和同支。
我们要去掉的重复，实际上是，同层不同支的情况。

const backTracking = () => {
  // 在这一次的 backTracking 函数中，for 循环内部，其实就是同层不同支的情况
  // 我们要在这个时候记录下，之前使用过的元素，并去重
  const used = [] // 我们在这一层声明一个 数组，用来记录使用过的元素
  for(...) {
    // 在这一层 for 循环时，我们来做去重
    if (used.includes(nums[i])) continue
    // 如果没使用过，就添加进去
    used.push(nums[i])
  }
}

三、具体代码

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var findSubsequences = function (nums) {
  const res = []
  const path = []
  const len = nums.length
  const backTracking = (start) => {
    if (path.length > 1) res.push(path.map(i => i))
    const used = [] // 用于记录同层不同支使用过的元素
    for (let i = start; i < len; i++) {
      if (path[path.length - 1] !== undefined && nums[i] < path[path.length - 1]
        || used.includes(nums[i])) continue
      used.push(nums[i])
      path.push(nums[i])
      backTracking(i + 1)
      path.pop()
    }
  }
  backTracking(0)
  return res
};

四、其他解法