leetcode491.递增子序列：HashSet同层去重与递增条件的双重保障

一、题目深度解析与子序列特性

题目描述

给定一个整数数组nums，找出所有长度至少为2的递增子序列，子序列不需要连续但必须满足递增顺序，且不能有重复的子序列。例如：

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

核心挑战：

1. 递增性保证：子序列元素必须非递减
2. 重复子序列去重：不同路径生成的相同子序列需去重
3. 子序列定义：无需连续，但顺序必须保持原数组中的相对顺序

二、回溯解法的核心实现与HashSet作用

完整回溯代码实现

class Solution {List<Integer> temp = new LinkedList<>();  // 存储当前子序列List<List<Integer>> res = new ArrayList<>();  // 存储所有结果子序列public List<List<Integer>> findSubsequences(int[] nums) {backtracking(nums, 0, temp);return res;}public void backtracking(int[] nums, int start, List<Integer> temp) {if (temp.size() > 1) {res.add(new ArrayList<>(temp));  // 收集长度≥2的子序列}HashSet<Integer> hs = new HashSet<>();  // 同层去重集合for (int i = start; i < nums.length; i++) {// 条件1：当前数字需≥子序列最后一个数字（递增）// 条件2：同层中已选过该数字则跳过（去重）if ((!temp.isEmpty() && nums[i] < temp.get(temp.size() - 1)) || hs.contains(nums[i])) {continue;}hs.add(nums[i]);  // 记录当前层已选数字temp.add(nums[i]);  // 选择当前数字backtracking(nums, i + 1, temp);  // 递归下一层temp.removeLast();  // 回溯：撤销选择}}
}

核心组件解析：

1. HashSet的作用：

   • 在每层循环中新建，用于记录当前层已选择的数字
   • 避免同一层中重复选择相同数字，防止生成重复子序列

2. 递增条件判断：

   if (!temp.isEmpty() && nums[i] < temp.get(temp.size() - 1))
   

   • 确保当前数字≥子序列最后一个数字，维持递增性

3. 结果收集时机：

   • 当temp.size() > 1时收集结果，满足长度≥2的要求

三、HashSet同层去重的核心逻辑

1. 为什么需要HashSet？

重复子序列产生场景：

• 当数组中有重复数字时，不同路径可能生成相同子序列
• 例如：数组[1,2,2]中，选择第一个2和第二个2会生成相同子序列[1,2]

HashSet的去重原理：

• 在每层循环中，HashSet记录当前层已选数字
• 同一层中遇到相同数字时跳过，确保同层不重复选择
• 不同层可以重复选择（如父层选第一个2，子层选第二个2）

2. HashSet的作用范围

作用域分析：

for (int i = start; i < nums.length; i++) {HashSet<Integer> hs = new HashSet<>(); // 每层循环新建HashSet// ...hs.add(nums[i]);// ...
}

• 同层唯一：每个循环层的HashSet独立，仅影响当前层的数字选择
• 跨层无关：父层和子层的HashSet互不影响，允许跨层选择相同数字

示例说明：

• 处理数组[4,7,7]时：
  1. 第一层循环（start=0）：
     • 选4，HashSet={4}
     • 递归到start=1，处理7
  2. 第二层循环（start=1）：
     • 选第一个7，HashSet={7}
     • 递归到start=2，处理第二个7
  3. 第三层循环（start=2）：
     • 选第二个7，HashSet={7}
     • 生成子序列[4,7,7]
  4. 同层中第二个7会被HashSet过滤，避免生成重复的[4,7,7]

四、递增条件与去重的协同工作

1. 递增条件的实现

代码逻辑：

if (!temp.isEmpty() && nums[i] < temp.get(temp.size() - 1))

• 空序列处理：temp为空时允许选第一个数字
• 递增判断：非空时当前数字需≥最后一个数字

示例验证：

• 数组[1,3,2]：
  • 选1后，只能选≥1的数字（3或2）
  • 选3后，只能选≥3的数字（无）
  • 选2时，2<3，被条件过滤，确保子序列递增

2. 双重条件的协同作用

条件组合：

if (递增条件 || 去重条件) continue;

• 递增条件：保证子序列递增
• 去重条件：保证同层不重复选数字
• 两者共同作用，确保结果合法且唯一

流程示例：

1. 处理数字序列[1,2,2]：
   • 第一层选1，temp=[1]
   • 第二层选第一个2，temp=[1,2]，合法
   • 第二层选第二个2时，HashSet已含2，跳过
   • 避免生成重复的[1,2]

五、算法流程深度模拟：以输入[4,6,7,7]为例

关键递归路径：

1. 初始状态：temp=[]，start=0

   • 进入循环，i=0选4，temp=[4]，递归start=1

2. 第一层递归（start=1，temp=[4]）：

   • i=1选6（6≥4），temp=[4,6]，加入res
   • 递归start=2，处理7
   • i=2选7（7≥6），temp=[4,6,7]，加入res
   • 递归start=3，处理7
     • i=3选7（7≥7），temp=[4,6,7,7]，加入res
   • 回溯到start=2，i=3的7被HashSet记录，同层不再选
   • i=2处理完毕，回溯到start=1
   • i=2选7（7≥4），temp=[4,7]，加入res
   • 递归start=3，选7，temp=[4,7,7]，加入res

3. 第二层递归（start=1，不选6选7）：

   • i=2选7（7≥4），temp=[4,7]，与之前的[4,7]是否重复？
   • 否，因为HashSet在不同层，允许跨层选7
   • 递归start=3，选7，生成[4,7,7]

六、HashSet去重的数学证明

命题：HashSet确保同层不重复选数字

证明步骤：

1. 同层唯一性：每层循环的HashSet独立，记录当前层已选数字
2. 跨层独立性：父层和子层的HashSet无关联，允许跨层选相同数字
3. 重复子序列防止：
   • 同层选相同数字会被HashSet过滤
   • 跨层选相同数字属于不同路径，生成不同子序列（如[4,7]和[4,7]实际是同一子序列？不，这里需要注意，跨层选相同数字可能生成相同子序列，所以必须通过HashSet在同层去重，跨层由于路径不同，但子序列可能相同，如何处理？）

哦，这里发现之前的理解有误：实际上，HashSet的作用是防止同一层中选择相同数字，从而避免同一层中生成重复子序列。例如，在同一层中如果有多个相同数字，只选第一个，后面的跳过，这样就不会在同一层中生成重复的子序列。而跨层选择相同数字是允许的，因为它们属于不同的路径，但生成的子序列可能相同吗？

例如，数组[2,2]，第一层选第一个2，递归选第二个2，生成[2,2]；第一层选第二个2时，由于HashSet在第一层中记录了第一个2，所以会跳过，确保只生成一次[2,2]。

七、算法复杂度分析

1. 时间复杂度

• O(2^n × n)：
  • 每个数字有选或不选两种状态，总共有2^n个子序列
  • 每个子序列需O(n)时间复制到结果集
  • 去重操作O(1)（HashSet查询）

2. 空间复杂度

• O(n)：
  • 递归栈深度最大为n
  • temp列表长度最多为n
  • 结果集空间O(2^n × n)

八、核心技术点总结：同层去重的三大关键

1. HashSet的作用域控制

• 每层新建：每层循环新建HashSet，确保同层去重
• 跨层独立：不同层的HashSet互不影响，允许跨层选相同数字

2. 递增条件的实现

• 前向比较：当前数字与子序列最后一个数字比较
• 空序列处理：空序列时允许选任意数字

3. 双重条件协同

• 递增条件：保证子序列合法性
• 去重条件：保证子序列唯一性
• 两者结合确保结果正确

九、常见误区与优化建议

1. HashSet位置错误

• 误区：将HashSet放在递归函数外

  HashSet<Integer> hs = new HashSet<>(); // 错误，跨层共享会导致去重过度
  

• 正确做法：放在循环内，每层独立

2. 递增条件错误

• 误区：使用nums[i] > temp.getLast()（严格递增）
• 正确逻辑：题目允许非递减，应使用nums[i] >= temp.getLast()

3. 优化建议：位运算去重（不推荐）

// 仅作示意，实际不适用
Set<List<Integer>> set = new HashSet<>();
// 生成所有子序列后去重

• 劣势：无法利用递增条件剪枝，效率更低

十、总结：同层去重与递增条件的协同设计

本算法通过回溯法结合HashSet同层去重，高效解决了递增子序列的生成与去重问题，核心在于：

1. HashSet的层内唯一性：每层循环新建HashSet，确保同层不重复选数字
2. 递增条件的前向判断：当前数字与子序列最后一个数字比较，维持递增性
3. 结果收集策略：子序列长度≥2时收集，满足题目要求

理解这种解法的关键是把握HashSet的作用域控制和递增条件的判断逻辑，两者共同作用确保了子序列的合法性和唯一性。这种同层去重策略在处理含重复元素的子序列问题中具有通用性，是回溯算法去重的经典实现。