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

解析

题目特点：

1. 找的子集严格递增
2. 子集至少有两个元素
3. 子集不能重复，但是子集中可以有重复元素

这也是一个回溯问题，在一个集合中找符合条件的子集基本都可以用回溯来解。该题中因为要避免子集树同一层出现重复元素，需要一个额外数组来存放重复的数字，也可以使用set和map，但是因为要频繁的插入数据，且元素个数不多，可以使用数组来存储。

[盗图]

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var findSubsequences = function(nums) {
  const res = [], temp = [];
  const len = nums.length;
  backtracing(0);
  return res;
  function backtracing(startIndex) {
    if(temp.length >= 2) res.push(Array.from(temp));
    const set = [];// 控制子集树中，本层不能出现相同的数字来避免重复
    for(let i = startIndex; i < len; i++) {
      const tlen = temp.length;
      if((tlen > 0 && nums[i] < temp[tlen - 1]) || set[nums[i]+100]) continue;
      set[nums[i]+100] = true;
      temp.push(nums[i]);
      backtracing(i+1);
      temp.pop();
      //注意这里不能使用set[nums[i]+100] = false，不然set的存在就毫无意义了
    }
  }
};