回溯三大题型：子集 · 排列 · 组合

三大题型的本质区别

子集（Subsets）   → 元素不重复使用，顺序不重要，每个元素选或不选
组合（Combinations）→ 元素不重复使用，顺序不重要，选够 k 个
排列（Permutations）→ 元素不重复使用，顺序重要，每次从剩余元素选

区分的核心：是否关心顺序、是否有固定大小限制。

通用回溯框架

void backtrack(/* 参数 */) {
    if (/* 终止条件 */) {
        result.add(new ArrayList<>(path));  // 注意要拷贝
        return;
    }
    for (int i = start; i < candidates.length; i++) {
        // 剪枝
        path.add(candidates[i]);     // 做选择
        backtrack(i + 1, ...);      // 递归（注意 start 的变化）
        path.remove(path.size() - 1); // 撤销选择
    }
}

子集（LeetCode 78）

无重复元素，生成所有子集：

List<List<Integer>> subsets(int[] nums) {
    List<List<Integer>> res = new ArrayList<>();
    backtrack(nums, 0, new ArrayList<>(), res);
    return res;
}

void backtrack(int[] nums, int start, List<Integer> path, List<List<Integer>> res) {
    res.add(new ArrayList<>(path));   // 每个节点都是一个子集（包括空集）
    for (int i = start; i < nums.length; i++) {
        path.add(nums[i]);
        backtrack(nums, i + 1, path, res);  // i+1：不能重复使用
        path.remove(path.size() - 1);
    }
}

子集问题的决策树：每次从 start 往后选，且 每次进入递归就记录答案。

含重复元素的子集（LeetCode 90）

先排序，跳过同层的重复选择：

List<List<Integer>> subsetsWithDup(int[] nums) {
    Arrays.sort(nums);
    List<List<Integer>> res = new ArrayList<>();
    backtrack(nums, 0, new ArrayList<>(), res);
    return res;
}

void backtrack(int[] nums, int start, List<Integer> path, List<List<Integer>> res) {
    res.add(new ArrayList<>(path));
    for (int i = start; i < nums.length; i++) {
        if (i > start && nums[i] == nums[i - 1]) continue;  // 同层去重
        path.add(nums[i]);
        backtrack(nums, i + 1, path, res);
        path.remove(path.size() - 1);
    }
}

去重口诀：先排序，同层跳重复（i > start && nums[i] == nums[i-1]）。

组合（LeetCode 77）

从 1..n 中选 k 个数的所有组合：

List<List<Integer>> combine(int n, int k) {
    List<List<Integer>> res = new ArrayList<>();
    backtrack(1, n, k, new ArrayList<>(), res);
    return res;
}

void backtrack(int start, int n, int k, List<Integer> path, List<List<Integer>> res) {
    if (path.size() == k) {
        res.add(new ArrayList<>(path));
        return;
    }
    // 剪枝：剩余元素不够 k-path.size() 个时提前退出
    for (int i = start; i <= n - (k - path.size()) + 1; i++) {
        path.add(i);
        backtrack(i + 1, n, k, path, res);
        path.remove(path.size() - 1);
    }
}

关键剪枝：i <= n - (k - path.size()) + 1，即从 i 开始至少还有 k - path.size() 个数。

组合总和（LeetCode 39）

元素可以重复使用，找和为 target 的组合：

List<List<Integer>> combinationSum(int[] candidates, int target) {
    Arrays.sort(candidates);
    List<List<Integer>> res = new ArrayList<>();
    backtrack(candidates, 0, target, new ArrayList<>(), res);
    return res;
}

void backtrack(int[] candidates, int start, int remain, List<Integer> path, List<List<Integer>> res) {
    if (remain == 0) { res.add(new ArrayList<>(path)); return; }
    for (int i = start; i < candidates.length; i++) {
        if (candidates[i] > remain) break;  // 已排序，后续更大，剪枝
        path.add(candidates[i]);
        backtrack(candidates, i, remain - candidates[i], path, res);  // i 不变：可重复用
        path.remove(path.size() - 1);
    }
}

排列（LeetCode 46）

无重复元素的全排列，用 used 数组标记：

List<List<Integer>> permute(int[] nums) {
    List<List<Integer>> res = new ArrayList<>();
    backtrack(nums, new boolean[nums.length], new ArrayList<>(), res);
    return res;
}

void backtrack(int[] nums, boolean[] used, List<Integer> path, List<List<Integer>> res) {
    if (path.size() == nums.length) {
        res.add(new ArrayList<>(path));
        return;
    }
    for (int i = 0; i < nums.length; i++) {
        if (used[i]) continue;
        used[i] = true;
        path.add(nums[i]);
        backtrack(nums, used, path, res);
        path.remove(path.size() - 1);
        used[i] = false;
    }
}

对比速查