4.1 回溯算法团灭子集、排列、组合问题

本文对应的力扣题目：

78.子集

46.全排列

77.组合

4.1.1 子集

问题很简单，输入一个不包含重复数字的数组，要求算法输出这些数字的所有子集。

解法一：

vector<vector<int>> subsets(vector<int>& nums) {
    // base case，返回一个空集
    if (nums.empty()) return {{}};
    // 把最后一个元素拿出来
    int n = nums.back();
    nums.pop_back();
    // 先递归算出前面元素的所有子集
    vector<vector<int>> res = subsets(nums);

    int size = res.size();
    for (int i = 0; i < size; i++) {
        // 然后在之前的结果之上追加
        res.push_back(res[i]);
        res.back().push_back(n);
    }
    return res;
}

解法二：

// 存储所有子集
vector<vector<int>> res;

/* 主函数 */
vector<vector<int>> subsets(vector<int>& nums) {
    // 记录走过的路径
    vector<int> track;
    backtrack(nums, 0, track);
    return res;
}

/* 套回溯算法模板 */
void backtrack(vector<int>& nums, int start, vector<int>& track) {
    // 前序遍历的位置
    res.push_back(track);
    // 从 start 开始，防止产生重复的子集
    for (int i = start; i < nums.size(); i++) {
        // 做选择
        track.push_back(nums[i]);
        // 递归回溯
        backtrack(nums, i + 1, track);
        // 撤销选择
        track.pop_back();
    }
}

4.1.2 组合

输入两个数字 n, k，算法输出 [1..n] 中 k 个数字的所有组合。

套回溯算法模板框架就行了：

// 记录所有组合
vector<vector<int>>res;

/* 主函数 */
vector<vector<int>> combine(int n, int k) {
    if (k <= 0 || n <= 0) return res;
    vector<int> track;
    backtrack(n, k, 1, track);
    return res;
}

// 套回溯算法模板
void backtrack(int n, int k, int start, vector<int>& track) {
    // 到达叶子节点才更新 res
    if (k == track.size()) {
        res.push_back(track);
        return;
    }
    // i 从 start 开始递增
    for (int i = start; i <= n; i++) {
        // 做选择
        track.push_back(i);
        // 递归回溯
        backtrack(n, k, i + 1, track);
        // 撤销选择
        track.pop_back();
    }
}

4.1.3 排列

输入一个不包含重复数字的数组 nums，返回这些数字的全部排列：

List<List<Integer>> res = new LinkedList<>();

/* 主函数，输入一组不重复的数字，返回它们的全排列 */
List<List<Integer>> permute(int[] nums) {
    // 记录「路径」
    LinkedList<Integer> track = new LinkedList<>();
    backtrack(nums, track);
    return res;
}

void backtrack(int[] nums, LinkedList<Integer> track) {
    // 到达叶子节点
    if (track.size() == nums.length) {
        res.add(new LinkedList(track));
        return;
    }
    
    for (int i = 0; i < nums.length; i++) {
        // 排除不合法的选择
        if (track.contains(nums[i]))
            continue;
        // 做选择
        track.add(nums[i]);
        // 进入下一层决策树
        backtrack(nums, track);
        // 取消选择
        track.removeLast();
    }
}