递增子序列

递增子序列

题目描述

给定一个整型数组, 你的任务是找到所有该数组的递增子序列，递增子序列的长度至少是2。

示例1

输入: [4, 6, 7, 7]
输出: [[4, 6], [4, 7], [4, 6, 7], [4, 6, 7, 7], [6, 7], [6, 7, 7], [7,7], [4,7,7]]

示例2

输入: [4, 3, 2, 1]
输出: []

题目分析

我们以[4, 6, 7, 7]为例子

• 一开始我们的数组为array = [4,6,7,7], 结果集为result = [], 暂存结果集为 prefix = [], 遍历数组
• 遍历开始，值为4, 放入暂存结果集，此时prefix = [4], 我们暂时不考虑顺序和是否重复，把剩下的数组继续递归遍历
• 此时 array = [6, 7, 7], 把 6 取出来，prefix = [4, 6], 此时 prefix 的长度 >= 2 放入 result，此时 result = [[4, 6]], 把剩下的[7,7]继续递归，回溯之后这层可以整 result = [[4,6],[4,7],[4,7]]， 不过这是回溯之后的结果
• 此时 array = [7, 7], prefix = [4, 6], reuslt = [[4, 6]]; 执行操作像上面一步

实现代码

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var findSubsequences = function(nums) {
    let result = [];
    contribute(result, nums, [])
    return result
};

var contribute = function(result, array, prefix) {
    let length = array.length;
    if(length == 0) {
        return result;
    }
    let isInlcude = [];

    for(let i = 0; i < length; i++) {
        if(isInlcude.includes(array[i])) { // 去重
            continue;
        }
        const last = prefix.length > 0 ? prefix[prefix.length - 1] : null;
        // 如果prefix 的最后一个数 比当前数要大，那就不符合，例如 prefix = [4, 5]; 此时last 应该是5，array[i] = 1, 5>1不符合题意 
        if(last !== null && last > array[i]) { 
            continue;
        }
        const temp = prefix.concat(array[i]);
        isInlcude.push(array[i])
        if(temp.length > 1) {
            result.push(temp);
        }
        contribute(result, array.slice(i + 1, array.length), temp);
    }
    return result
}