递增子序列 图解题解

这道题到底在问什么

输入

[4,6,7,7]

长度≥2

至少两个数

不下降

后≥前

输出

[[4,6],[4,6,7],[4,6,7,7],[4,7],[4,7,7],[6,7],[6,7,7],[7,7]]

最优解：一步一步想明白

1. 3组合题常用「排序 + 跳过相邻相同」去重。但这题求的是子序列——必须保持原数组顺序，一排序就破坏了顺序关系，[3,1,2] 排完成了 [1,2,3]，意义全变了。所以这条路走不通，得换个去重办法。
2. 4用回溯逐个往后挑数：每选一个数就从它后面继续选（start 保证只往后、维持原顺序），且要求新数 ≥ path 末尾来保证不下降。path 长度到 2 就随时收一个。选→递归→撤销，老三步。
3. 5去重靠一个本层 set：在同一个递归层里（同一个父节点下），如果某个数值已经被选过当过分支头，再遇到相同数值就跳过。注意是「同层」，不同层的相同数值（比如两个 7 一前一后被选进同一条 path）是允许的。下面用 [4,6,7,7] 走一遍。
4. 6start=0，path=[]，results 空开搜：path 还是空的，4 个数（下标 0~3 = 4,6,7,7）都没用过。从下标 0 开始，逐个挑头。先看下标 0 的 4。
5. 7start=0 → 选 nums[0]=4，本层 set={4}顶层第一个选 4，path=[4]。本层 set 记下 {4}。长度才 1，还不能收（要 ≥2）。接着从下标 1 往后，找 ≥4 的数继续接。
6. 86 ≥ 4 ✓，len=2 → 收！在 [4] 后面选 6：6 ≥ 4 满足不下降，path=[4,6]，长度到 2 了，收下 [4,6]！还能再往后接，继续。
7. 97 ≥ 6 ✓，len=3 → 收！在 [4,6] 后面选下标 2 的 7：7 ≥ 6，path=[4,6,7]，收下 [4,6,7]。还有下标 3 的另一个 7 可以接。
8. 107 ≥ 7 ✓（不下降允许相等），len=4 → 收！在 [4,6,7] 后面选下标 3 的 7：7 ≥ 7 也算不下降（允许相等），path=[4,6,7,7]，收下 [4,6,7,7]！后面没数了，撤销这个 7 往回退。
9. 11pop → path=[4,6,7]，下标3的7变回可选撤销刚收进来的下标 3 的 7，path 退回 [4,6,7]，下标 3 重新变回可选（灰恢复）。[4,6,7] 这层后面已经没有数了，继续往上退回 [4,6]。
10. 12撤销 7 → 回到 path=[4,6]，本层 set 已含 {7}撤销下标 3 的 7，退回到 [4,6] 这一层。刚才在这层已经拿下标 2 的 7 当过分支头，本层 set 里记着 {7}。下一个候选是下标 3 的 7——数值也是 7，要看会不会被去重挡住。
11. 13nums[3]=7 已在本层 set 中 → skip（打叉）同层去重实演：在 [4,6] 这层，下标 2 的 7 已经当过分支头，本层 set 含 7。现在下标 3 又是 7，同一层同数值不能再开第二个分支，直接跳过（打叉那个）。否则会重复搜出一模一样的 [4,6,7…]。[4,6] 这层探完，撤销 6。
12. 14撤销 6 → path=[4]，本层 set={4,6}，再选 7撤销 6 回到 [4] 这层。本层（[4] 之后这一层）刚才拿 6 当过分支头，set 含 {6}，现在换下标 2 的 7：7 ≥ 4，path=[4,7]，收下 [4,7]。注意 6 已撤走、重新变回可选。
13. 157 ≥ 7 ✓，len=3 → 收！在 [4,7] 后面接下标 3 的 7：7 ≥ 7 满足，path=[4,7,7]，收下 [4,7,7]。这是不同层的两个 7（一个当头、一个接尾），允许同时进 path。后面没数，撤销回退。
14. 16本层 set 含 7（下标2选过）→ nums[3]=7 skip退回 [4] 这层，本层在下标 2 选过 7，set 含 7。轮到下标 3 的 7：数值重复，同层跳过（打叉）。4 打头的所有分支探完，撤销 4，顶层换下一个头。
15. 17顶层 set={4,6}，选 nums[1]=6撤销 4，顶层 set 现在含 {4}，换选下标 1 的 6 当头，path=[6]。4 已不在 path（恢复成可选）。长度才 1 不收，从下标 2 往后接 ≥6 的数。
16. 187 ≥ 6 ✓，len=2 → 收！在 [6] 后面选下标 2 的 7：7 ≥ 6，path=[6,7]，收下 [6,7]！本层 set 记下 {7}。继续往后接。
17. 197 ≥ 7 ✓，len=3 → 收！在 [6,7] 后接下标 3 的 7：7 ≥ 7，path=[6,7,7]，收下 [6,7,7]。撤销回退。
18. 20本层 set 含 7 → nums[3]=7 skip退回 [6] 这层，本层在下标 2 选过 7，下标 3 又是 7，同层跳过（打叉）。6 打头探完，撤销 6，顶层再换头。
19. 21顶层 set={4,6,7}，选 nums[2]=7撤销 6，顶层换选下标 2 的 7 当头，path=[7]，顶层 set 记下 {…,7}。长度 1 不收，往后接 ≥7 的数。
20. 227 ≥ 7 ✓，len=2 → 收！在 [7] 后面接下标 3 的 7：7 ≥ 7，path=[7,7]，收下 [7,7]！这是最后一个解。撤销回到顶层。
21. 23顶层 set 已含 7（下标2当过头）→ nums[3]=7 skip回到顶层，下标 2 的 7 已经当过头、顶层 set 含 7，下标 3 的 7 数值重复，同层跳过（打叉）。所有分支探尽。
22. 24结果 = 8 个不下降子序列整棵搜索树走完，8 个不下降子序列全部收齐，没有一个重复。「同层 set 去重」是这题不出重复的核心，「新数 ≥ path 末尾」保证不下降。
23. 27三个机制各管一件事：传 i+1 维持原数组顺序（这是子序列的本质），新数 ≥ 末尾保证不下降，每层独立的 set 拦住同层重复值。三者合起来才能不漏不重地搜全。
24. 30全局 set 含 7 → [6,7] 想接的 7 被误杀负例：如果 used 是全局的，4 打头时已经把 7 加进 set 了；轮到 [6] 想接 7 时，7 被全局 set 误判为「用过」直接跳过（打叉），[6,7]、[6,7,7] 全被漏掉。所以 used 必须每层各一个、进函数才新建。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

class Solution:
    def findSubsequences(self, nums):
        ans = []
        path = []
        def backtrack(start):
            if len(path) >= 2:
                ans.append(path[:])
            used = set()              # 本层去重
            for i in range(start, len(nums)):
                if path and nums[i] < path[-1]:
                    continue          # 不下降
                if nums[i] in used:       # 同层重复
                    continue
                used.add(nums[i])
                path.append(nums[i])
                backtrack(i + 1)
                path.pop()
        backtrack(0)
        return ans

class Solution {
public:
    vector<vector<int>> ans;
    vector<int> path;
    vector<vector<int>> findSubsequences(vector<int>& nums) {
        backtrack(0, nums);
        return ans;
    }
    void backtrack(int start, vector<int>& nums) {
        if (path.size() >= 2) ans.push_back(path);
        unordered_set<int> used;          // 本层去重
        for (int i = start; i < (int)nums.size(); ++i) {
            if (!path.empty() && nums[i] < path.back())
                continue;                 // 不下降
            if (used.count(nums[i])) continue; // 同层重复
            used.insert(nums[i]);
            path.push_back(nums[i]);
            backtrack(i + 1, nums);
            path.pop_back();
        }
    }
};

class Solution {
    private List<List<Integer>> ans = new ArrayList<>();
    private List<Integer> path = new ArrayList<>();
    public List<List<Integer>> findSubsequences(int[] nums) {
        backtrack(0, nums);
        return ans;
    }
    private void backtrack(int start, int[] nums) {
        if (path.size() >= 2) ans.add(new ArrayList<>(path));
        Set<Integer> used = new HashSet<>();   // 本层去重
        for (int i = start; i < nums.length; ++i) {
            if (!path.isEmpty() && nums[i] < path.get(path.size() - 1))
                continue;                      // 不下降
            if (used.contains(nums[i])) continue;  // 同层重复
            used.add(nums[i]);
            path.add(nums[i]);
            backtrack(i + 1, nums);
            path.remove(path.size() - 1);
        }
    }
}

def bt(start):
    if len(path) >= 2: res.append(path[:])
    used = set()                 # 每层新建
    for i in range(start, n):
        if path and a[i] < path[-1]: continue   # 约束
        if a[i] in used: continue    # 同层去重
        used.add(a[i])
        path.append(a[i])
        bt(i + 1)                # 关键 i+1
        path.pop()

复杂度

面试官可能追问