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：

输入：nums = [4,4,3,2,1]
输出：[[4,4]]

提示：

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

回溯

元素递增的长度大于等于2的元素可重不可复选的组合，

class Solution {
    public List<List<Integer>> findSubsequences(int[] nums) {
        if (nums.length == 0) {
            return res;
        }
        
        backtrack(nums, 0);
        return res;
    }

    List<List<Integer>> res = new LinkedList<>();
    // 记录回溯的路径
    List<Integer> track = new LinkedList<>();

    // 回溯算法主函数
    void backtrack(int[] nums, int start) {
        if (track.size() >= 2) {
            // 找到一个合法答案，不能返回，还要继续找。重点。
            res.add(new LinkedList<>(track));
        }
        
        // 用哈希集合防止重复选择相同元素，横向作用。为什么不能用全局used数组去重？
        // 因为组合问题的下一轮递归会执行i+1，所以一定不会访问到used[i]，所以used[i]没有意义。
        // 排列问题才需要used数组。
        // 题目要求不能排序。
        Set<Integer> used = new HashSet<>();
        // 回溯算法标准框架
        for (int i = start; i < nums.length; i++) {
            // 不能选比前一个元素小的，不能选本轮已选的。
            // 纵向对比递增，横向剪枝，保证集合中元素都是递增顺序。重点。
            if (!track.isEmpty() && track.getLast() > nums[i]) {
                continue;
            }
            // 横向对比去重，横向剪枝，确保递增，即不要重复使用相同的元素，重点。
            if (used.contains(nums[i])) {
                continue;
            }
            
            // 选择 nums[i]
            used.add(nums[i]);
            track.add(nums[i]);
            // 递归遍历下一层回溯树
            backtrack(nums, i + 1);
            // 撤销选择 nums[i]
            track.removeLast();
            // 这里不能写used.remove(nums[i])，因为used是当前递归层的状态，不是全局状态。重点。
        }
    }
}

在上述代码中，track.removeLast() 是用来撤销之前对 track 集合的操作，确保回溯算法能够回到选择 nums[i] 之前的状态。这是标准的回溯算法操作，用来确保每次回溯后状态都能恢复到选择当前元素之前的样子。

而 used 集合在这个场景中扮演的是在同一层级中防止选择重复元素的角色。它不是用来记录全局的状态，而是记录当前递归层（或称“树层”）的状态。每次进入一个新的递归层（即在 for 循环的一次迭代中），used 都会被重新创建，仅用于这一层迭代中防止选择重复的元素。这意味着在当前递归层结束时，used 的状态自然而然地就被“撤销”了，因为它只在当前层有效。

加入 used.remove(nums[i]) 不仅是多余的，还可能导致错误。因为这样做可能会允许在同一递归层的后续迭代中选择一个本应在该层被视为已使用的元素。例如，假如 nums 中有重复的 3，并且在某层第一次选择了 3，如果在撤销选择后移除了 3 的使用标记，那么同层的后续迭代中又可以再次选择 3，这会导致生成重复的子序列。因此，正确的操作是保持 used 在整个递归层有效，而不是跨递归层次使用。

总结：在这种回溯算法中，used 仅在同一递归层中管理状态，而不跨递归层共享，因此不需要在撤销操作时移除元素，以保持其在当前递归层的一致性。

上述代码的时空复杂度主要取决于两个因素：输入数组 nums 的长度 n 和生成的结果子序列的数量。下面分别对时间复杂度和空间复杂度进行分析：

时间复杂度

1. 递归深度与迭代次数：递归的深度最多可以达到 n，因为最长的路径是遍历整个数组。在每一层递归中，for 循环会遍历从 start 开始到数组结束的所有元素。

2. HashSet操作：在每层递归中，对于 HashSet 的操作（add 和 contains）都是 O(1) 的时间复杂度。

3. 子序列生成：最坏情况下，即每次都能生成有效的递增子序列时，生成的子序列数量和其长度都会对时间复杂度有贡献。由于每个元素可以选择加入或不加入子序列，生成的子序列总数接近 2^n，但因为题目中要求至少两个元素，实际数目会少一些。

总的时间复杂度为 O(n * 2^n)。这里 n 是用于每一层循环的复杂度估算，2^n 是由于每个元素都有加入或不加入子序列的选择。

空间复杂度

1. 递归栈空间：递归的深度最多为 n，因此递归栈的空间复杂度是 O(n)。

2. 临时存储空间：track 和 used 都是临时存储结构，其中 track 的最大长度为 n，而 used 是一个固定长度为 9 的布尔数组（因为输入元素值从 1 到 9），所以这部分空间复杂度也是 O(n)。

3. 输出空间：存储结果r的空间复杂度取决于生成的子序列数量和长度，这在最坏情况下接近 O(2^n * n)。

综合上述因素，整体空间复杂度是 O(n + 2^n * n)，其中主要空间消耗来源于输出结果的存储。