491. Increasing Subsequences

[Tcdian]

491. Increasing Subsequences

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

Example

Input: [4, 6, 7, 7]
Output: [[4, 6], [4, 7], [4, 6, 7], [4, 6, 7, 7], [6, 7], [6, 7, 7], [7,7], [4,7,7]]

Note

• 给定数组的长度不会超过15。
• 数组中的整数范围是 [-100,100]。
• 给定数组中可能包含重复数字，相等的数字应该被视为递增的一种情况。

[Tcdian]

Solution

• JavaScript Solution

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var findSubsequences = function(nums) {
    const sub = [];
    const unique = new Set();
    const result = [];
    backtracking(0);
    return result;

    function backtracking(index) {
        if (index >= nums.length) {
            if (sub.length >= 2 && !unique.has(sub.join())) {
                result.push([...sub]);
                unique.add(sub.join());
            }
            return;
        }
        if (sub.length === 0 || sub[sub.length - 1] <= nums[index]) {
            sub.push(nums[index]);
            backtracking(index + 1);
            sub.pop();
        }
        backtracking(index + 1);
    }
};

• TypeScript Solution

function findSubsequences(nums: number[]): number[][] {
    const sub: number[] = [];
    const unique = new Set();
    const result: number[][] = [];
    backtracking(0);
    return result;

    function backtracking(index: number) {
        if (index >= nums.length) {
            if (sub.length >= 2 && !unique.has(sub.join())) {
                result.push([...sub]);
                unique.add(sub.join());
            }
            return;
        }
        if (sub.length === 0 || sub[sub.length - 1] <= nums[index]) {
            sub.push(nums[index]);
            backtracking(index + 1);
            sub.pop();
        }
        backtracking(index + 1);
    }
};