递增子序列如何用回溯去重？为什么每层要用 used 集合？

简化版

递增子序列要求保持原数组顺序，并且长度至少为 2。

回溯时从当前位置往后选数，如果当前数小于路径最后一个数，就不能选。

由于数组可能有重复值，同一层递归要用 used 集合避免选择相同数字，防止生成重复子序列。

详细版

递归函数 dfs(start) 表示接下来可以从下标 start 开始选择元素。

如果 path.length >= 2，当前路径就是一个合法递增子序列，可以加入答案。然后继续尝试后面的元素。

每层创建一个 used 集合，记录这一层已经尝试过哪些数。如果同一层再次遇到相同值，跳过。

注意不能先排序，因为子序列必须保持原数组相对顺序。排序会改变题目语义。

完整版教学

一、子序列和子集有什么不同

子集问题通常可以先排序再做同层去重，因为元素顺序不重要。但子序列要求保持原数组相对顺序，不能排序。比如 [4,6,7,7] 中 [4,7] 可以来自不同下标，但结果只需要一份；同时 [6,4] 不能出现，因为它违背原顺序和递增条件。

易错点：子序列问题不能随便排序，排序会改变可选顺序。

二、递增条件怎么维护

路径 path 保存当前已经选择的子序列。新候选 nums[i] 必须满足：

path 为空，或者 nums[i] >= path[path.length - 1]

这里是非严格递增，所以允许相等。例如 [7,7] 是合法递增子序列。如果题目要求严格递增，条件才改为 >。

三、为什么每层要用 used

重复来自同一层选择了相同值。以 [4,6,7,7] 为例，在某一层如果第一个 7 已经作为“本层选择值 7”探索过，那么第二个 7 再作为同层起点会生成重复结果。每层的 used 集合只限制当前层，不限制不同深度，因为不同深度选择相同值可能是合法的 [7,7]。

去重范围	是否正确	原因
全局 used	错误	会禁止合法重复值
每层 used	正确	只去掉同层重复分支
不去重	错误	会产生重复子序列

这就是这题去重最关键的点。

四、代码模板

实现如下：

function findSubsequences(nums) {
  const ans = []
  const path = []

  function dfs(start) {
    if (path.length >= 2) ans.push([...path])
    const used = new Set()
    for (let i = start; 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.pop()
    }
  }

  dfs(0)
  return ans
}

used 放在递归函数内部，意味着每一层都有自己的去重集合。

五、带数字推演

数组 [4,6,7,7]。当路径是 [4,6] 时，后面两个 7 都能接上，但在同一层只允许第一个 7 开启分支。进入下一层后，路径变成 [4,6,7]，另一个 7 又可以被选择，形成 [4,6,7,7]。

同层重复：跳过
不同层重复：允许

这句话能帮你区分去重边界。

六、常见误区与追问

• 误区：先排序再回溯。 子序列必须保持原数组顺序，排序会改变答案集合。
• 误区：用全局 Set 禁止重复数字。 会错误删除 [7,7] 这类合法结果。
• 误区：只在加入答案时用字符串 Set 去重。 能兜底但效率差，也没有体现回溯剪枝能力。
• 追问：为什么 path.length >= 2 就加入？ 题目要求长度至少 2，后续还能继续延长当前路径。
• 追问：递增是严格的吗？ 标准题通常是非严格递增，即允许相等。

这些问题考的是“顺序约束”和“同层去重”。

七、加强记忆

递增子序列记成“不能排序，路径递增，同层去重”。候选必须不小于路径末尾；长度达到 2 就可以收集；每层用一个 used 集合跳过相同起始值。全局禁止重复会误杀合法重复，同层去重才是刚刚好。