递增子序列

Question

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

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

思路

简单来说就是判断子集是否为递增的

判断的逻辑应该放在path.push之前

如果当前元素值小于子序列最后一个元素，不继续向下递归
如果遇到相同元素，不继续向下递归（去重）

此处去重的逻辑与子集II不同，因为在本题中不能改变nums数组的排列顺序

var findSubsequences = function(nums) {
    const res = []  // 结果[][]
    const path = [] // 每次递归的结果[]
    // startIndex ：每次递归的起使位置
    const backtracking = (startIndex)=>{
        const used = []
        for(let i=startIndex;i<nums.length;i++){	// 本层集合中元素
            if(path.length!=0 && nums[i]<path[path.length-1]) continue  //当前元素值小于子序列最后一个元素
            if(i>0 && used[nums[i]+100]===1) continue	//去重操作
            path.push(nums[i])				// 处理节点
            used[nums[i]+100]=1
            if(path.length>1)    res.push([...path])
            backtracking(i+1)		// 递归
            path.pop()					//回溯
        }
    }
    backtracking(0)
    return res
};

递增子序列 ​

思路 ​

递增子序列

思路