题目描述

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

样例

输入：[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]]

说明

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

算法

(递归回溯) $O(n2^n)$

1. 采用递归的实现策略，递归状态为：当前已经递归到了第 d 个数字且记录下了之前选的子序列 cur。递归出口为 d 已经到了数组末尾。
2. 如果 cur 的长度大于等于 2，直接累计答案。
3. 在每一层递归时，从第 d 个数字开始（含）向后寻找下一个数字，这里需要用一个 unordered_set 记录当前层已经枚举过的数字。若找到比 cur 末尾不小的数字，且这个数字在当前层是第一次出现。假设找到的是第 i 个数字，则 cur 记录下 nums[i]，然后递归到第 i+1 个数字继续下去。

时间复杂度

• 最坏情况下，每个数字都有两个选择，选或者不选，故总共可能有 $2^n$ 个答案，累计答案需要 $O(n)$ 的时间，故总时间复杂度为 $O(n2^n)$。

空间复杂度

• 递归需要 $O(n)$ 的系统栈空间，答案需要 $O(n2^n)$ 的空间。

C++ 代码

class Solution {
public:
    void solve(int d, vector<int>& cur, const vector<int>& nums, vector<vector<int>>& ans) {
        if (cur.size() >= 2)
            ans.push_back(cur);

        if (d == nums.size())
            return;

        unordered_set<int> vis;

        for (int i = d; i < nums.size(); i++)
            if ((cur.size() == 0 || nums[i] >= *cur.rbegin())
              && vis.find(nums[i]) == vis.end()) {

                cur.push_back(nums[i]);
                solve(i + 1, cur, nums, ans);
                cur.pop_back();
                vis.insert(nums[i]);
            }
    }

    vector<vector<int>> findSubsequences(vector<int>& nums) {
        vector<int> cur;
        vector<vector<int>> ans; 
        solve(0, cur, nums, ans);
        return ans;
    }
};