使用回溯算法解决排列组合问题

  回溯算法是一种非常实用的算法解题思路，LeetCode中题库中有106道回溯的试题，而且难度都在中等以上，掌握回溯算法对高效快速解决很多问题都很有帮助。今天我们主要看看回溯算法的解题套路和实用回溯解决排列组合问题的题解。

1.回溯算法特点

  回溯算法过程：在搜索中寻找问题的解，发现不满足条件时，就回溯返回上一步，尝试别的路径。
  从上面的定义可以看出，回溯算法依赖于递归实现，与递归算法的差异就在于一个“回”字，即修改了状态并做了尝试之后，需要回过来把状态改回去再做其他尝试，通过多轮回溯逐步求出所有的解。
  回溯算法的应用：回溯算法特别使用用于有排列组合或者路径探索的场景。

2.使用回溯解决组合问题

2.1 n个数中的k个组合

77. 组合
剑指 Offer II 080. 含有 k 个元素的组合
题目描述：给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
先上源码如下：

class Solution {
public:
    vector<vector<int>> combine(int n, int k) {
        backtrack(n, k, 1);
        return res;
    }
private:
    vector<vector<int>> res;
    vector<int> temp;
    void backtrack(int n, int k, int index){
        if(temp.size() == k){ //递归结束条件
            res.push_back(temp);
            return;
        }
        for(int i = index; i <= n && temp.size() < k; i++){
            temp.push_back(i); //修改状态
            backtrack(n, k, i+1); //递归回溯
            temp.pop_back();  //改回状态
        }
    }
};

解题分析：

1. 定义变量：排列组合问题一般会返回一个二维数组的结果，这里定义了成员变量vector<vector> res，还会需要一个探索过程中的一维数组临时变量vector temp。
2. 定义回溯函数：回溯函数依赖递归实现，入口函数不方便递归，一般都写一个递归子函数backtrack来完成。
3. 定义回溯函数参数列表：一般是入口函数参数列表+ 递归索引位置（组合问题用来取不同的数据元素）
4. 定义递归结束条件
5. 回溯实现：组合问题数据元素不重复，因此一般都是循环遍历每个元素然后回溯处理

按照以上套路，组合问题可以很容易解决

2.2 子集

78. 子集
剑指 Offer II 079. 所有子集
题目描述：给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集。

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        res.push_back({});
        backtrack(nums, 0);
        return res;
    }
private:
    void backtrack(const vector<int>& nums, int start){
        for(int i = start; i < nums.size(); i++){
            temp.push_back(nums[i]);
            res.push_back(temp);
            backtrack(nums, i+1);
            temp.pop_back();
        }
    }
    vector<vector<int>> res;
    vector<int> temp;
};

90. 子集 II
接下来题目稍微修改一下，有重复元素的子集
题目描述：给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。
题目解析：有重复元素的组合，需要先对数据元素排序，然后在做组合时排除重复组合

class Solution {
public:
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        res.push_back({});
        sort(nums.begin(), nums.end());
        backtrack(nums, 0);
        return res;
    }
private:
    void backtrack(const vector<int>& nums, int start){
        for(int i = start; i < nums.size(); i++){
            if(i > start && nums[i] == nums[i-1])
                continue;
            temp.push_back(nums[i]);
            res.push_back(temp);
            backtrack(nums, i+1);
            temp.pop_back();
        }
    }
    vector<int> temp;
    vector<vector<int>> res;
};

2.3 组合总和

40. 组合总和 II
题目描述：给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用一次。
题目分析：与上面的组合问题相似，只是多了求和问题

class Solution {
public:
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        sort(candidates.begin(), candidates.end());
        backtrack(candidates, 0, target);
        return res;
    }
private:
    void backtrack(const vector<int>& candidates, int index, int target){
        if(target == 0) {
            res.push_back(temp);
            return;
        }
        for(int i = index; i < candidates.size() && target-candidates[i] >= 0; i++){
            if(i > index && candidates[i] == candidates[i-1])
                continue;
            temp.push_back(candidates[i]);
            backtrack(candidates, i+1, target-candidates[i]);
            temp.pop_back();
        }
    }
    vector<int> temp;
    vector<vector<int>> res;
};

题目再变一下，原始数据中的每个数据元素可以用多次。
39. 组合总和
题目描述：给定一个无重复元素的正整数数组 candidates 和一个正整数 target ，找出 candidates 中所有可以使数字和为目标数 target 的唯一组合。candidates 中的数字可以无限制重复被选取。
题目分析：数据元素可以重复使用，那就不能遍历组合了，这里递归地多次选择某个元素，直到总和超过target.

class Solution {
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        backtrack(candidates, target, 0);
        return res;
    }
private:
    void backtrack(const vector<int>& nums, int target, int index){
        if(index >= nums.size()) return;
        if(target == 0) {
            res.push_back(temp);
            return;
        }
        backtrack(nums, target, index+1);
        if(target-nums[index] >= 0){
            temp.push_back(nums[index]);
            backtrack(nums, target-nums[index], index);
            temp.pop_back();
       }
    }
    vector<vector<int>> res;
    vector<int> temp;
};

3.使用回溯解决排列问题

3.1 全排列

46. 全排列
剑指 Offer II 083. 没有重复元素集合的全排列
题目描述：给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列。你可以 按任意顺序 返回答案。
题目分析：排列问题数据的访问需要增加一个访问标志visited，避免出现排列中出现相同元素，回溯时也要改为visited状态

class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> res;
        visited.resize(nums.size());
        permute(nums, res);
        return res;
    }
private:
    vector<int> temp;
    vector<bool> visited;
    void permute(vector<int>& nums, vector<vector<int>>& res){
        if(temp.size() == nums.size()){
            res.push_back(temp);
            return;
        }
        for(int i = 0; i < nums.size(); i++){
            if(!visited[i]){
                temp.push_back(nums[i]);
                visited[i] = true;
                permute(nums, res);
                visited[i] = false;
                temp.pop_back();
            }
        }
    }    
};

3.2 不重复的全排列

47. 全排列 II
剑指 Offer II 084. 含有重复元素集合的全排列
题目描述：给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。
题目分析：有重复元素的组合，需要先对数据元素排序，然后在做排列时排除重复组合

class Solution {
public:
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        sort(candidates.begin(), candidates.end());
        backtrack(candidates, 0, target);
        return res;
    }
private:
    void backtrack(const vector<int>& candidates, int index, int target){
        if(target == 0) {
            res.push_back(temp);
            return;
        }
        for(int i = index; i < candidates.size() && target-candidates[i] >= 0; i++){
            if(i > index && candidates[i] == candidates[i-1])
                continue;
            temp.push_back(candidates[i]);
            backtrack(candidates, i+1, target-candidates[i]);
            temp.pop_back();
        }
    }
    vector<int> temp;
    vector<vector<int>> res;
};