解决排列和子集问题的回溯算法

216. 组合总和 III

39. 组合总和

40. 组合总和 II

46. 全排列

47. 全排列 II

77. 组合

78. 子集

90. 子集 II

以上是力扣设计相关问题的题目。排列组合还是子集问题无非就是从序列 nums 中以给定规则取若干元素，主要有以下几类：

1. 元素无重不可复选，即 nums 中的元素都是唯一的，每个元素最多只能被使用一次，这也是最基本的形式。
2. 元素可重不可复选，即 nums 中的元素可以存在重复，每个元素最多只能被使用一次。
3. 元素无重可复选，即 nums 中的元素都是唯一的，每个元素可以被使用若干次。

以组合为例：

1.如果输入 nums = [2,3,6,7]，和为 7 的组合应该只有 [7]

2.如果输入 nums = [2,5,2,1,2]，和为 7 的组合应该有两种 [2,2,2,1] 和 [5,2]

3.如果输入 nums = [2,3,6,7]，和为 7 的组合应该有两种 [2,2,3] 和 [7]

上面用组合问题举的例子，但排列、组合、子集问题都可以有这三种基本形式，所以共有 9 种变化。

除此之外，题目也可以再添加各种限制条件，比如让你求和为 target 且元素个数为 k 的组合，那这么一来又可以衍生出一堆变体，所以一般笔试很喜欢出这种题。

但无论怎么变化，其本质就是穷举所有解，而这些解呈现树形结构，使用回溯算法框架再稍微修改一些细节即可把这些问题一网打尽。

回溯算法框架代码如下：

import java.util.ArrayList;
import java.util.List;

public class BacktrackExample {

    private List<List<Object>> result = new ArrayList<>();

    public void backtrack(List<Object> path, List<Object> choices) {
        if (满足结束条件(path)) {
            result.add(new ArrayList<>(path));
            return;
        }

        for (Object choice : choices) {
            // 做选择
            path.add(choice);
            
            // 递归
            backtrack(path, choices);
            
            // 撤销选择
            path.remove(path.size() - 1);
        }
    }

    private boolean 满足结束条件(List<Object> path) {
        // 这里实现满足结束条件的逻辑
        return false; // 示例返回，替换为实际逻辑
    }

    public List<List<Object>> getResult() {
        return result;
    }

}

问题一：当元素无重不可复选时，即 nums 中的元素都是唯一的，每个元素最多只能被使用一次：

// 组合/子集问题回溯算法框架
void backtrack(int[] nums, int start) {
    // 回溯算法标准框架
    for (int i = start; i < nums.length; i++) {
        // 做选择
        track.addLast(nums[i]);
        // 注意参数
        backtrack(nums, i + 1);
        // 撤销选择
        track.removeLast();
    }
}

// 排列问题回溯算法框架
void backtrack(int[] nums) {
    for (int i = 0; i < nums.length; i++) {
        // 剪枝逻辑
        if (used[i]) {
            continue;
        }
        // 做选择
        used[i] = true;
        track.addLast(nums[i]);

        backtrack(nums);
        // 撤销选择
        track.removeLast();
        used[i] = false;
    }
}

 问题二：元素可重不可复选，即 nums 中的元素可以存在重复，每个元素最多只能被使用一次，其关键在于排序和剪枝

Arrays.sort(nums);
// 组合/子集问题回溯算法框架
void backtrack(int[] nums, int start) {
    // 回溯算法标准框架
    for (int i = start; i < nums.length; i++) {
        // 剪枝逻辑，跳过值相同的相邻树枝
        if (i > start && nums[i] == nums[i - 1]) {
            continue;
        }
        // 做选择
        track.addLast(nums[i]);
        // 注意参数
        backtrack(nums, i + 1);
        // 撤销选择
        track.removeLast();
    }
}


Arrays.sort(nums);
// 排列问题回溯算法框架
void backtrack(int[] nums) {
    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;
        track.addLast(nums[i]);

        backtrack(nums);
        // 撤销选择
        track.removeLast();
        used[i] = false;
    }
}

问题三：元素无重可复选，即 nums 中的元素都是唯一的，每个元素可以被使用若干次，只要删掉去重逻辑即可：

// 组合/子集问题回溯算法框架
void backtrack(int[] nums, int start) {
    // 回溯算法标准框架
    for (int i = start; i < nums.length; i++) {
        // 做选择
        track.addLast(nums[i]);
        // 注意参数
        backtrack(nums, i);
        // 撤销选择
        track.removeLast();
    }
}

// 排列问题回溯算法框架
void backtrack(int[] nums) {
    for (int i = 0; i < nums.length; i++) {
        // 做选择
        track.addLast(nums[i]);
        backtrack(nums);
        // 撤销选择
        track.removeLast();
    }
}

只要从树的角度思考，这些问题看似复杂多变，实则改改 base case 就能解决。只要熟悉了该框架，再细致了解一下细节问题，相信排列组合子集问题都不是问题。