DataStructure_Algorithm_HandBook_PreForLeetCode

491. Non-decreasing Subsequences

Given an integer array nums, return all the different possible non-decreasing subsequences of the given array with at least two elements. You may return the answer in any order.

Example 1:

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

Example 2:

Input: nums = [4,4,3,2,1]
Output: [[4,4]]

Constraints:

• 1 <= nums.length <= 15
• -100 <= nums[i] <= 100

solution

这里也会遇到同层选到两个一样的数字的问题，因此我们也要考虑同层去重的问题，但是这里不能简单的排序然后相邻的元素比较来去重，因为排序会改变数组的顺序，所以这边我们就新开一个 set 来去重复。

var findSubsequences = function(nums) {
    let result = [];
    dfs(0, [], nums, result);
    return result;
};

function dfs(index, path, nums, result) {
    if (path.length >= 2) {
        result.push([...path]);
    }
    let used = new Set();  // 在这一层递归中已使用的元素
    //或者也可以用一个 200 大小的数组来替代set，会更快，但是无所谓
    for (let i = index; i < nums.length; i++) {
        if (used.has(nums[i])) continue;  // 避免在同一层递归中使用重复的元素
        if (path.length > 0 && nums[i] < path[path.length - 1]) continue;
        used.add(nums[i]);
        path.push(nums[i]);
        dfs(i + 1, path, nums, result);
        path.pop();
    }
}

注意这里的set应该在每次递归调用中根据当前的索引和路径动态管理，而不是全局地管理。这是因为在不同的递归层次中，相同的数字可能是有效的，只要它们是递增的。

所以不能用一个全局的Set来避免选择相同的元素