子集、排列与去重技巧

前两篇把组合和切割的模板讲透了，这篇处理剩下的两大类：子集和排列，以及本专题最烧脑的部分——去重。三块内容其实是三个独立的"开关"：改变收集时机、取消 startIndex、排序后剪枝，每个开关对应一个套路。

子集（78）：收集树的所有节点

78. 子集：返回数组所有子集（幂集），元素互不重复。

组合/切割问题的答案都藏在叶子节点上（凑满 k 个、切到串尾才收）；子集问题不同——树上每个节点都是一个合法的子集。空集、单元素、部分组合、全集，一个都不能漏。

nums = [1,2,3]，搜索树（每一步是"是否纳入当前元素"的逐位延伸）：
 
              []
         /    |    \
       [1]   [2]   [3]
      /  \     |
   [1,2] [1,3] [2,3]
     |
   [1,2,3]
 
★ 7 个节点 = 7 个非空子集，全都要收集

这决定了子集问题和组合的两个差异：

收集时机：进入递归函数第一件事就收，而不是在终止条件里收；
终止条件：可以不写显式终止——for 循环的边界天然保证 startIndex 越界后递归结束，收获发生在进函数的一瞬间。

注意到上面的搜索树里有 7 个节点（不含根），但正确答案是 8 个子集——根节点的空集也算。所以写法上有个关键细节：收集动作放在递归函数入口处，第一次调用时 path 为空，空集自然被收进来。完整代码出奇地短：

class Solution {
    List<List<Integer>> result = new ArrayList<>();
    Deque<Integer> path = new ArrayDeque<>();
 
    public List<List<Integer>> subsets(int[] nums) {
        backtracking(nums, 0);
        return result;
    }
 
    private void backtracking(int[] nums, int startIndex) {
        result.add(new ArrayList<>(path));       // 每个节点都是子集，先收
        for (int i = startIndex; i < nums.length; i++) {
            path.addLast(nums[i]);               // 做选择
            backtracking(nums, i + 1);           // 起点 +1：子集内部有序、防重复
            path.removeLast();                   // 撤销选择
        }
    }
}

注意子集依然要传 i + 1：子集内元素顺序无所谓，[1,3] 和 [3,1] 算同一个子集，startIndex 的防重复作用和组合完全一致。

排列（46）：used 数组取消 startIndex

46. 全排列：返回不含重复数字的数组的所有排列。

排列和组合的核心区别是顺序有意义：[1,2] 和 [2,1] 是两个答案。所以同一层里，前面层用过的元素本层要"重新有资格"被选——每层的选择列表都从下标 0 开始，startIndex 的闸门被取消。

但闸门取消了，怎么知道哪些元素已经被当前路径占用？引入 used[] 数组：

class Solution {
    List<List<Integer>> result = new ArrayList<>();
    Deque<Integer> path = new ArrayDeque<>();
    boolean[] used;
 
    public List<List<Integer>> permute(int[] nums) {
        used = new boolean[nums.length];
        backtracking(nums);
        return result;
    }
 
    private void backtracking(int[] nums) {
        // 终止条件：排列攒够 n 个元素
        if (path.size() == nums.length) {
            result.add(new ArrayList<>(path));
            return;
        }
        // 每层都从 0 开始扫，靠 used 跳过已占用的元素
        for (int i = 0; i < nums.length; i++) {
            if (used[i]) continue;   // 已经在 path 里了，跳过
            used[i] = true;          // 做选择：标记占用
            path.addLast(nums[i]);
            backtracking(nums);      // 递归
            path.removeLast();       // 撤销选择：解除标记
            used[i] = false;
        }
    }
}

记忆口诀：组合看起点（startIndex），排列看标记（used）。组合用"起点递增"保证不重复消费；排列每层都要消费"所有还没被消费的"，只能靠标记数组。

去重核心：树层去重 vs 树枝去重

输入数组本身含重复元素时（如 [1,2,2]），穷举会产生重复结果。套路是固定的两步：先排序让相等元素相邻，再用 used[i-1] 判断去重。难点在于判断式的两种语义。

用图理解两种去重

对排序后的 [1,2,2]，我们给两个 2 编号区分：2₁、2₂（实际值相同）。

树层去重：同一层里，前一个相同的元素"刚被撤销"，如果还选它，就会生成和兄弟分支一模一样的子树。目的是让这一层跳过重复候选：

              []
        /     |     \
     [1]    [2₁]    [2₂] ✗ ← 树层去重：和 [2₁] 分支重复，剪掉
    /   \     |
[1,2₁] [1,2₂]✗ [2₁,2₂]
   |      |
[1,2₁,2₂] [1,2₂,2₁]✗ ← 也是重复，同样靠这条规则剪掉

树枝去重：在同一条递归链上（从根到当前节点），相同的元素允许连续使用——这正是全排列需要的：[2₁,2₂] 是合法排列，不能被误杀。

两种语义共用一个判断式 used[i-1] && nums[i]==nums[i-1]，配合不同的遍历起点产生不同效果：

写法 A（i 从 startIndex 起）：判断为 true 时跳过 → 树层去重。同一层中 2₁ 的分支撤销后 used[2₁] 仍为 true？不对——撤销后会置 false，所以同一层到 2₂ 时 used[i-1]==false，还需要换成 !used[i-1] 才是树层语义。请看下面代码里的注释，这是全文最需要注意的地方。

// 树层去重版（适用于子集II、组合总和II）
// nums 已排序
for (int i = startIndex; i < nums.length; i++) {
    // 同层中：前一个相同元素已经"用完并被撤销"（used=false），
    // 说明以它开头的分支刚被完整搜索过，再选当前元素必然重复
    if (i > startIndex && nums[i] == nums[i - 1]) continue;
 
    used[i] = true;
    path.addLast(nums[i]);
    backtracking(nums, i + 1);
    path.removeLast();
    used[i] = false;
}

写法 B（i 从 0 起 + used）：适用于全排列 II。同一层里如果 nums[i] == nums[i-1] 且 used[i-1] == false（说明同层的 i-1 分支刚做完被撤销），跳过 → 树层去重；如果 used[i-1] == true（说明 i-1 在当前路径上），允许选 → 树枝延续。

// 全排列II：树层去重 + 树枝放行，nums 已排序
for (int i = 0; i < nums.length; i++) {
    if (used[i]) continue; // 树枝：当前路径已占用
    // 树层去重：i-1 同值且未在路径上，说明它的分支刚被搜完
    if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) continue;
 
    used[i] = true;
    path.addLast(nums[i]);
    backtracking(nums);
    path.removeLast();
    used[i] = false;
}

两种写法本质是同一个原理：排序后，相同元素组里"首个未使用的"才有资格开新分支。!used[i-1] 时剪（树层），used[i-1] 时放行（树枝）。把这半句话想通，90 和 47 两道题共用同一把钥匙。

子集 II（90）完整代码

90. 子集 II：数组含重复元素，返回所有子集（去重）。

class Solution {
    List<List<Integer>> result = new ArrayList<>();
    Deque<Integer> path = new ArrayDeque<>();
 
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums); // 去重前提：先排序
        backtracking(nums, 0);
        return result;
    }
 
    private void backtracking(int[] nums, int startIndex) {
        result.add(new ArrayList<>(path)); // 子集：每个节点都收
        for (int i = startIndex; i < nums.length; i++) {
            // 树层去重：同层同值只走第一个分支
            if (i > startIndex && nums[i] == nums[i - 1]) continue;
            path.addLast(nums[i]);
            backtracking(nums, i + 1);
            path.removeLast();
        }
    }
}

三类问题对比总表

组合、子集、排列的所有差异浓缩成一张表，做题前先对号入座：

要素	组合	子集	排列
防重复手段	startIndex	startIndex	used[] 数组
下一层起点	i + 1（可重复选取时传 i）	i + 1	无起点概念，每层从 0 扫
收集时机	只收叶子（满足条件时）	每个节点都收	只收叶子（size == n）
需要排序吗	无重复元素不需要	含重复元素需要	含重复元素需要
去重判断	i > startIndex 同值剪	i > startIndex 同值剪	i > 0 且 !used[i-1] 同值剪
时间复杂度	O(k × C(n,k))	O(n × 2^n)	O(n × n!)

复杂度与易错点

复杂度：子集有 2^n 个解，每个拷贝 O(n)，时间 O(n × 2^n)；排列有 n! 个解，每个拷贝 O(n)，时间 O(n × n!)。去重的排序开销 O(n log n) 可忽略。
易错点：
1. 忘记排序：去重判断依赖相等元素相邻，不排序判断式失效；
2. 判断条件写成 used[i-1] 用于树层去重：方向反了会变成树枝放行，把该剪的分支全放出来；
3. 90 题在子集里去重后忘了收集发生在进函数处：如果照抄组合的"叶子收集"，会漏掉大量子集；
4. 47 题中 i > 0 与 i > startIndex 混用：排列没有 startIndex，判断恒用 i > 0。

LeetCode 题目清单

78. 子集：收集时机前移到"进函数即收"，终止条件可以省略。
90. 子集 II：排序 + 树层去重与"每个节点都收"的组合拳。
491. 递增子序列：不能排序（要保原始顺序），用每层哈希 set 做同层去重——去重的另一种武器。
46. 全排列：used[] 标记 + 取消 startIndex 的奠基题。
47. 全排列 II：used 数组同时承担树枝占用与树层去重双职责。

参考

代码随想录 · 回溯算法专题