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个元素或以上）之前我们写的去重方法都是先排序，然后定义used数组。但是本题中不能用这种方法，应该在每一层递归树上定义一个使用过的数组来记录该层上元素是否使用过。其他方面都和子集题类似。

javascript

var findSubsequences = function (nums) {

    var results = []
    //used 数组其实可以去掉
    var findSubsequencesInner = function (nums, index, currentResults, used) {
        //当本分支上的元素个数大于等于2，加入结果
        if (currentResults.length >= 2) {
            results.push(currentResults)
        }
        //这里可以不用，因为要递归到最底层
        if (index >= nums.length) {
            return
        }
        //定义当前循环层的used数组
        const usedInCurrentLevel = []
        for (let i = index; i < nums.length; i++) {
            const currentValue = nums[i]
            //如果当前树层有过使用记录，则不进行递归
            const hasFound = usedInCurrentLevel.filter(one => one === nums[i]).length
            if (hasFound) {
                continue
            }
            const previousValue = currentResults[currentResults.length - 1]
            //这里判断是否有序，为空时自然有序，否则看结果集里最后一个和当前比，保持currentResults有序
            if (currentResults.length === 0 || previousValue <= nums[i]) {
                used[i] = true //used 可以去掉
                //这里是当前递归树的一层记录
                usedInCurrentLevel.push(nums[i])
                findSubsequencesInner(nums, i + 1, [...currentResults, nums[i]], used)
                used[i] = false //used 可以去掉
            }
        }
    }
    var used = Array(nums.length).fill(false)
    findSubsequencesInner(nums, 0, [], used)

    console.log(JSON.stringify(results))
    return results
};

491 递增子序列 ​

题解 ​

491 递增子序列

题解