回溯算法：排列、组合、子集

回溯算法框架

回溯是一种通过深度优先搜索枚举所有可能的决策树算法，遇到不满足条件的分支就"剪枝"回头。

// 通用框架
void backtrack(参数，选项列表，当前路径) {
    if (满足结束条件) {
        结果集.add(当前路径的副本);
        return;
    }
    for (选项 in 选项列表) {
        // 做选择
        当前路径.add(选项);
        backtrack(参数，缩小后的选项列表，当前路径);
        // 撤销选择
        当前路径.removeLast();
    }
}

三要素：

1. 路径：当前已做的选择
2. 选择列表：当前可做的选择
3. 结束条件：何时停止并记录结果

子集（Subsets）

问题：给定不含重复元素的整数数组，返回所有可能的子集。

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);       // 撤销
    }
}

输出：[], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3]（共 2ⁿ 个）

含重复元素的子集 II

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);
    }
}
// 调用前需先：Arrays.sort(nums);

组合（Combinations）

问题：从 1 到 n 中选取 k 个数，返回所有组合。

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

void backtrack(int n, int k, int start, List<Integer> path, List<List<Integer>> res) {
    if (path.size() == k) {
        res.add(new ArrayList<>(path));
        return;
    }
    // 剪枝：剩余元素数量 >= 还需要的元素数量
    for (int i = start; i <= n - (k - path.size()) + 1; i++) {
        path.add(i);
        backtrack(n, k, i + 1, path, res);
        path.remove(path.size() - 1);
    }
}

剪枝关键：i <= n - (k - path.size()) + 1，若剩余数字不够凑满 k 个，直接停止。

组合总和（元素可重复使用）

List<List<Integer>> combinationSum(int[] candidates, int target) {
    List<List<Integer>> res = new ArrayList<>();
    Arrays.sort(candidates);
    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 不是 i+1（可重复）
        path.remove(path.size() - 1);
    }
}

排列（Permutations）

问题：给定不含重复元素的数组，返回所有全排列。

List<List<Integer>> permute(int[] nums) {
    List<List<Integer>> res = new ArrayList<>();
    boolean[] used = new boolean[nums.length];
    backtrack(nums, used, 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;
    }
}

含重复元素的全排列 II

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;
        // 跳过重复：同一层中，若当前元素与前一个相同且前一个未使用（说明是同层重复）
        if (i > 0 && nums[i] == nums[i-1] && !used[i-1]) continue;
        used[i] = true;
        path.add(nums[i]);
        backtrack(nums, used, path, res);
        path.remove(path.size() - 1);
        used[i] = false;
    }
}
// 调用前：Arrays.sort(nums);

关键模式：子集 vs 组合 vs 排列

小结

1. 模板：做选择 → 递归 → 撤销选择
2. 剪枝：排序后剪掉不可能的分支（if (x > remain) break）
3. 去重：排序后跳过相邻相同元素（if (i > start && nums[i] == nums[i-1]) continue）
4. 回溯的时间复杂度通常是指数级，这是问题本身决定的（枚举所有可能）