子集组合排列

Posted on Edited on Symbols count in article: 7.9k Reading time ≈ 7 mins.

零. 子集、组合和排列问题汇总

  • 组合问题和子集问题是等价的
  • 参考labuladong和优秀题解

一. 子集问题

78 子集划分

1.1 子集扩张

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        if(nums.empty())
            return vector<vector<int>>(1, vector<int>());
        int last = nums.back(); nums.pop_back();
        vector<vector<int>> sub = subsets(nums);
        int sz = sub.size();
        for(int i=0; i<sz; ++i){
            vector<int> tmp = sub[i];
            tmp.push_back(last);
            sub.push_back(tmp);
        }
        return sub;
    }
};

1.2 回溯1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    vector<vector<int>> ret;
    vector<int> cur;
    void traceback(vector<int>& nums, int pos){
        if(pos == nums.size()){
            ret.push_back(cur);
            return;
        }
        // 选
        cur.push_back(nums[pos]);
        traceback(nums, pos+1);
        cur.pop_back();
        
        // 不选
        traceback(nums, pos+1);
    }
    
    vector<vector<int>> subsets(vector<int>& nums) {
        traceback(nums, 0);
        return ret;
    }
};

1.3 回溯2(★)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    vector<vector<int>> ret;
    vector<int> cur;
    void traceback(vector<int>& nums, int pos){
        ret.push_back(cur);
        for(int i=pos; i<nums.size(); ++i){
            cur.push_back(nums[i]);
            traceback(nums, i+1);
            cur.pop_back();
        }
    }
    
    vector<vector<int>> subsets(vector<int>& nums) {
        traceback(nums, 0);
        return ret;
    }
};

90 子集划分Ⅱ

  1. 两条值相同的相邻树枝会产生重复，如果一个节点有多条值相同的树枝相邻，则只遍历第一条，剩下的都剪掉，不要去遍历（不能让队员越权）
  2. “使用过”在这个树形结构上是有两个维度的，一个维度是同一树枝上使用过，一个维度是同一树层上使用过。 我们要去重的是同一树层上的“使用过”，同一树枝上的都是一个组合里的元素，不用去重。（注意：这里的同一树层指的是由同一个父节点引出的子节点，叔伯的子节点可以用相同下一个值，比如下图[1]接2和[2]接2，都可以用2；但是[1]接2就不能接2'了！）
labuladong图示 LC-90

2.1 回溯1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
    vector<int> cur;
    vector<vector<int>> ret;

    void traceback(bool choosePre, int pos, vector<int> &nums) {
        if (pos == nums.size()) {
            ret.push_back(t);
            return;
        }
        // 不选
        traceback(false, cur + 1, nums);
        
        // 要在 [选] 之前执行，要在 [不选] 之后执行
        if (!choosePre && pos > 0 && nums[pos - 1] == nums[pos]) return;
        
        // 选
        cur.push_back(nums[pos]);
        traceback(true, pos + 1, nums);
        cur.pop_back();
    }

    vector<vector<int>> subsetsWithDup(vector<int> &nums) {
        sort(nums.begin(), nums.end());
        traceback(false, 0, nums);
        return ret;
    }
};

2.2 回溯2(★)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    vector<vector<int>> ret;
    vector<int> cur;
    void backtrack(vector<int>& nums, int pos){
        ret.push_back(cur);
        for(int i=pos; i<nums.size(); ++i){
            // i从pos开始，天然可以判定同一父节点的子节点们不会重复
            // 即只让重复段的第一个节点的树向下生长
            // 如果i从0开始，无法确定pos-1位置是否使用过，需要
            // 借助一个used数组
            if(i > pos && nums[i] == nums[i-1]) continue;
            cur.push_back(nums[i]);
            backtrack(nums, i+1);
            cur.pop_back();
        }
    }
    
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        sort(nums.begin(), nums.end()); // 要排序
        backtrack(nums, 0);
        return ret;
    }
};

2.3 回溯2（易读版利用used判断树层重复）

也可用used数组来简化理解，nums[i]与nums[i-1]相等，且nums[i-1]没有使用的情况下，表明重复了，因为只有在nums[i-1]用过之后才会不用，而nums[i-1]之前用过，其后的子树是已经加入到结果了，即可跳过当前点 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
private:
    vector<vector<int>> ret;
    vector<int> cur;
    void backtracking(vector<int>& nums, int pos, vector<bool>& used) {
        ret.push_back(cur);
        for (int i = pos; i < nums.size(); i++) {
            // used[i-1] == true，说明同一树支nums[i-1]使用过
            // used[i-1] == false，说明同一树层nums[i-1]使用过
            // 而我们要对同一树层使用过的元素进行跳过
            if (i > 0 && nums[i] == nums[i - 1] && !used[i-1]) continue;
            used[i] = true;
            cur.push_back(nums[i]);
            backtracking(nums, i + 1, used);
            cur.pop_back();
            used[i] = false;
        }
    }

public:
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        vector<bool> used(nums.size(), false);
        sort(nums.begin(), nums.end()); // 去重需要排序
        backtracking(nums, 0, used);
        return ret;
    }
};

二. 组合问题

39 组合总数

1.1 回溯

nums中的每个数字可以多次使用 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    vector<vector<int>> ret;
    vector<int> cur;
    void backtrack(vector<int>& nums, int pos, int target){
        if(target <= 0){
            if(target == 0) ret.push_back(cur);
            return;
        }
        for(int i=pos; i<nums.size(); ++i){
            cur.push_back(nums[i]);
            backtrack(nums, i, target-nums[i]); // 依旧传入i
            cur.pop_back();
        }
    }
    vector<vector<int>> combinationSum(vector<int>& nums, int target) {
        backtrack(nums, 0, target);
        return ret;
    }
};

2. 40 组合总数Ⅱ

nums中的每个数字在每个组合中只能使用一次 && 解集不能包含重复的组合。

说这是一个组合问题，其实换个问法就变成子集问题了：请你计算 candidates 中所有和为 target 的子集。

2.1 回溯1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
    vector<vector<int>> ret;
    vector<int> cur;
    void backtrack(vector<int>& nums, int pos, int target, bool preUsed){
        if(target < 0) return;
        if(target == 0){
            ret.push_back(cur);
            return;
        }
        if(pos >= nums.size()) return; // 不能放前面
        if(nums[pos] > target) return; // 剪枝：当前和后面的不可能会选
        
        // 不选
        backtrack(nums, pos+1, target, false);
        
        if(pos>0 && nums[pos-1] == nums[pos] && !preUsed) return;
        
        // 选
        cur.push_back(nums[pos]);
        backtrack(nums, pos+1, target - nums[pos], true);
        cur.pop_back();
    }
    vector<vector<int>> combinationSum2(vector<int>& nums, int target) {
        sort(nums.begin(), nums.end());
        backtrack(nums, 0, target, false);
        return ret;
    }
};

2.2 回溯2(★)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    vector<vector<int>> ret;
    vector<int> cur;
    void backtrack(vector<int>& nums, int pos, int target){
        if(target == 0){
            ret.push_back(cur);
            return;
        }
        for(int i=pos; i<nums.size(); ++i){
            if(i>pos && nums[i-1] == nums[i]) continue; // 值相同的树枝，只遍历第一条，防止重复
            if(target < nums[i]) return; // 剪枝：当前和后面的不可能会选
            cur.push_back(nums[i]);
            backtrack(nums, i+1, target-nums[i]);
            cur.pop_back();
        }
    }
    vector<vector<int>> combinationSum2(vector<int>& nums, int target) {
        sort(nums.begin(), nums.end());
        backtrack(nums, 0, target);
        return ret;
    }
};

三. 排列问题

1. 46 全排列

不含重复数字的数组：nums，经典回溯 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    vector<vector<int>> ret;
    vector<int> cur;
    void backtrack(vector<int>& nums, vector<bool>& used){
        if(cur.size() == nums.size()){
            ret.push_back(cur);
            return;
        }
        for(int i=0; i<nums.size(); ++i){
            if(used[i]) continue;
            used[i] = true;
            cur.push_back(nums[i]);
            backtrack(nums, used);
            cur.pop_back();
            used[i] = false;
        }
    }
    vector<vector<int>> permute(vector<int>& nums) {
        vector<bool> used(nums.size(), false);
        backtrack(nums, used);
        return ret;
    }
};

2. 47 全排列Ⅱ

含有重复数字的数组：nums

2.1 哈希（有意思）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
    vector<vector<int>> res;
    
    void traceback(map<int, int>& hash, vector<int>& cur, int n){
        if(cur.size() == n){
            res.push_back(cur);
            return;
        }
        for(map<int, int>::iterator itr=hash.begin(); itr!=hash.end(); ++itr){
            if(itr->second){
                --itr->second;
                cur.push_back(itr->first);
                traceback(hash, cur, n);
                cur.pop_back();
                ++itr->second;
            }
        }
    }
    
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        map<int, int> hash;
        vector<int> cur;
        for(auto e: nums) ++hash[e];
        traceback(hash, cur, nums.size());
        return res;
    }
};

2.2 回溯(跟子集问题2.3很像)

当出现重复元素时，比如输入 nums = [1,2,2',2'']，2' 只有在 2 已经被使用的情况下才会被选择，2'' 只有在 2' 已经被使用的情况下才会被选择，这就保证了相同元素在排列中的相对位置保证固定。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
    vector<vector<int>> ret;
    vector<int> cur;
    void backtrack(vector<int>& nums, vector<bool>& used){
        if(cur.size() == nums.size()){
            ret.push_back(cur);
            return;
        }
        for(int i=0; i<nums.size(); ++i){
            // i从0开始，固定相同的元素在排列中的相对位置
            if(i>0 && nums[i]==nums[i-1] && !used[i-1]) continue;
            if(used[i]) continue;
            used[i] = true;
            cur.push_back(nums[i]);
            backtrack(nums, used);
            cur.pop_back();
            used[i] = false;
        }
    }
    
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        sort(nums.begin(), nums.end()); // 必须排序
        vector<bool> used(nums.size(), false);
        backtrack(nums, used);
        return ret;
    }
};