排列组合问题

相关题目

• 78. 子集
• 90. 子集Ⅱ
• 77. 组合
• 39. 组合总和
• 40. 组合总和Ⅱ
• 216. 组合总和Ⅲ
• 46. 全排列
• 47. 全排列Ⅱ

主要形式

1. 元素不重复，不可以复选
2. 元素有重复，不可以复选
3. 元素不重复，可以复选（使用若干次）

主要思路

回溯算法框架

• 子集/组合问题
  子集和组合问题是等价的

• 全排列问题

子集

元素无重不可复选

• 题目

• 回溯树 为了防止出现重复的子集，需要保证元素之间的相对顺序不变，如只能是[2,3,1]，不能是[3,2,1]。
  假设根节点为第0层，那么第n层就是大小为n的所有子集。
  要计算所有的子集，只需要遍历这颗树，把所有节点的值收集起来

• 代码

class Solution {
private:
    vector<vector<int>> res;
    vector<int> track;//记录每一个子节点的值
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        if(nums.size()==0) return res;
        backtrace(nums,0);//遍历子树
        return res;
    }
    void backtrace(vector<int> nums,int start){//start为子树的层数
        res.emplace_back(track);//每个节点的值都是一个子集
        for(int i=start;i<nums.size();i++){//遍历每一个选项
            track.emplace_back(nums[i]);
            backtrace(nums,i+1);//向下遍历
            track.pop_back();
        }
    }
};

用start来避免生成重复子集
当start==nums.size退出循环

组合

元素无重不可复选

• 题目
• 思路 在[1,n]中大小为k的所有组合，即大小为k的子集，只需要回溯树中第k层的节点值
• 代码

class Solution {
private:
    vector<vector<int>> res;
    vector<int> track;
public:
    vector<vector<int>> combine(int n, int k) {
        backtrace(n,k,1);
        return res;
    }
    void backtrace(int n,int k,int start){
        if(track.size()==k){
            res.emplace_back(track);
            return;
        }
        for(int i=start;i<=n;i++){
            track.emplace_back(i);
            backtrace(n,k,i+1);
            track.pop_back();
        }
    }
};

控制算法仅收集第k层节点的值

排列

元素无重不可复选

• 题目
• 思路
  在组合/子集问题中，使用了start保证nums[start]之后只会出现nums[start+..]的元素，保证不出现重复子集。
  在全排列问题中，需要穷举元素的位置，nums[start]之后可以出现nums[start+..] 元素，所以不能再使用start。额外使用used数组来标记哪些元素还可以被选择。
• 代码

class Solution {
private:
    vector<vector<int>> res;
    vector<int> track;
    vector<int> used;
public:
    vector<vector<int>> permute(vector<int>& nums) {
        used.resize(nums.size(),0);
        traceback(nums);
        return res;
    }

    void traceback(vector<int> nums){
        if(track.size()==nums.size()){
            res.emplace_back(track);
            return;
        }
        for(int i=0;i<nums.size();i++){
            if(used[i]==1) continue;
            used[i]=1;
            track.emplace_back(nums[i]);
            traceback(nums);
            used[i]=0;
            track.pop_back();
        }
    }
};

用used标记已经在路径上的元素
收集叶子节点上的值

如果题目不要求全排列，只要第k层的节点值，可改为：

    void traceback(vector<int> nums,int k){
        if(track.size()==k){
            res.emplace_back(track);
            return;
        }
        for(int i=0;i<nums.size();i++){
            if(used[i]==1) continue;
            used[i]=1;
            traceback(nums,k);
            used[i]=0;
        }
    }

子集/组合

元素可重不可复选

• 题目
• 思路 我们可以先对数组进行排序，让相等的元素都靠在一起，那么如果有节点的值相同，其在树中也是相邻的，我们只遍历第一条，剩下的都剪掉
• 代码

class Solution {
private:
    vector<vector<int>> res;
    vector<int> track;
public:
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        sort(nums.begin(),nums.end());//先对数组排序，让相等的元素靠在一起
        traceback(nums,0);
        return res;
    }
    void traceback(vector<int> nums,int start){
        res.emplace_back(track);
        for(int i=start;i<nums.size();i++){
            if(i>start&&nums[i]==nums[i-1]) continue;
            track.emplace_back(nums[i]);
            traceback(nums,i+1);
            track.pop_back();
        }
    }
};

前面提到，组合与子集问题是等价的，下面是一道组合的题目

• 题目
• 思路
  同上，只需要记录元素和，改一下base case
• 代码

class Solution {
private:
    vector<vector<int>> res;
    vector<int> track;
    int tracksum;
public:
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        sort(candidates.begin(),candidates.end());//相同元素靠在一起，方便剪枝
        traceback(candidates,target,0);
        return res;
    }
    void traceback(vector<int> nums,int target,int start){
        if(tracksum==target){//找到目标组合
            res.emplace_back(track);
            return;
        }
        if(tracksum>target) return;//当前和大于目标值，不再继续遍历
        for(int i=start;i<nums.size();i++){
            if(i>start&&nums[i]==nums[i-1]) continue;//剪掉重复元素
            tracksum+=nums[i];
            track.emplace_back(nums[i]);
            traceback(nums,target,i+1);
            tracksum-=nums[i];
            track.pop_back();
        }
    }
};

排列

元素可重不可复选

• 题目
• 代码

class Solution {
private:
    vector<vector<int>> res;
    vector<int> track;
    vector<int> used;
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        used.resize(nums.size(),0);
        sort(nums.begin(),nums.end());
        traceback(nums);
        return res;
    }
    void traceback(vector<int>& nums){
        if(track.size()==nums.size()){
            res.emplace_back(track);
            return;
        }
        for(int i=0;i<nums.size();i++){
            if(used[i]) continue;
            if(i>0&&nums[i]==nums[i-1]&&!used[i-1]) continue;//保证相同元素间的相对位置不改变
            used[i]=1;
            track.emplace_back(nums[i]);
            traceback(nums);
            used[i]=0;
            track.pop_back();
        }
    }
};

• 思路 首先，对nums进行了排序，是为了保证相同元素靠在一起，防止出现重复子集；
  元素已经使用，需要剪枝；
  另外一种需要剪枝，比如已经出现[1,2，2',2'']，那么就不应该出现[1,2',2,2'']，做法是先保证2,2',2''的相对顺序不变，对于2'，一定只能出现在2之后，2''只能出现在2'之后，所以有

if(i>0&&nums[i]==nums[i-1]&&!used[i-1]) continue;

子集/组合

元素无重可复选

• 题目
• 思路 对于之前的题目，我们为了避免重复使用某一个元素，会将i+1变成下一个start，而这道题可以重复使用元素i,因此我们可以再次将i传给start，相当于给回溯树增加了一条树枝，这条树枝上一个元素可以被无限次使用；
  为了避免这棵树无法停止，需要设置合适的base case结束算法，即路径和大于target就没必要遍历了。
• 代码

class Solution {
private:
    vector<vector<int>> res;
    vector<int> track;
    int tracksum;
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        traceback(candidates,target,0);
        return res;
    }
    void traceback(vector<int> nums,int target,int start){
        if(tracksum==target){
            res.push_back(track);
            return;
        }
        if(tracksum>target) return;
        for(int i=start;i<nums.size();i++){
            tracksum+=nums[i];
            track.emplace_back(nums[i]);
            traceback(nums,target,i);
            tracksum-=nums[i];
            track.pop_back();
        }
    }
};

全排列

元素不重复可复选

• 思路 前面我们使用了used数组来保证不会使用同一个元素，如果可复选，那么只需要去掉used有关剪枝逻辑
• 代码

class Solution {
private:
    vector<vector<int>> res;
    vector<int> track;
public:
    vector<vector<int>> combinationSum(vector<int>& nums) {
        traceback(nums);
        return res;
    }
    void traceback(vector<int> nums){
        if(track.size()==nums.size()){
            res.push_back(track);
            return;
        }
        for(int i=0;i<nums.size();i++){
            track.emplace_back(nums[i]);
            traceback(nums);
            track.pop_back();
        }
    }
};