剑指offer专项突击版第28天

剑指 Offer II 082. 含有重复元素集合的组合

递归实现指数枚举，使用一些剪枝。
对枚举获得的组合，使用特殊手法对一些重复的组合去重：

1. 序列排序后，只要当前和前一个元素相同且前一个元素不在组合中，那么当前元素就不能选取至组合中。
2. 有一序列 b a a 容易想到会·出现重复的情况：1、b a a 2、b a a，这两种重复了，而 a 同时选取则不会重复： b a a。

class Solution {
public:
    vector<int> tmp;
    vector<vector<int>> res;
    bool st[110] = {0};
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        sort(candidates.begin(),candidates.end());
        dfs(0,candidates,target);
        return res;
    }
    void dfs(int x, vector<int> &candidates, int target) { 
        if(x > candidates.size()) return;
        if(target == 0) {
            res.emplace_back(tmp);
            return;
        }

        for(int i = x; i < candidates.size(); i++) {
            const auto &num = candidates[i];
            if(target >= num) {
                //排除会出现重复的组合
                if(i > 0 && num == candidates[i-1] && !st[i-1]) continue;
                tmp.emplace_back(num);
                st[i] = true;
                dfs(i+1,candidates,target-num);
                tmp.pop_back();
                st[i] = false;
            }
        }

    }
};
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
30
31
32

---

剑指 Offer II 083. 没有重复元素集合的全排列

经典的 $dfs$ 全排列，$st[i]$ 标记 $nums[i]$ 是否被选取。总共选取 $nums.size()$ 个，$x$ 表示选取了几个。

class Solution {
public:
    bool st[20] = {0};
    vector<vector<int>> res;
    vector<vector<int>> permute(vector<int>& nums) {
        vector<int> tmp;
        dfs(0,nums,tmp);
        return res;
    }
    void dfs(int x, vector<int> & nums, vector<int> &tmp) {
        if(x == nums.size()) {
            res.emplace_back(tmp);
            return;
        }
        for(int i = 0; i < nums.size(); i++) {
            if(!st[i]) {
                st[i] = true;
                tmp.push_back(nums[i]);
                dfs(x+1,nums,tmp);
                tmp.pop_back();
                st[i] = false;
            }
        }
    }
};
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

---

剑指 Offer II 084. 含有重复元素集合的全排列

全排列+组合去重（前两题结合）

class Solution {
public:
    vector<vector<int>> res;
    vector<int> tmp;
    bool st[10] = {0};
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        dfs(0,nums);
        return res;
    }
    void dfs(int x, vector<int> &nums) {
        if(x == nums.size()) {
            res.emplace_back(tmp);
            return;
        }
        for(int i = 0; i < nums.size(); i++) {
            if(!st[i]) {
                if(i > 0 && nums[i-1] == nums[i] && !st[i-1]) continue;
                st[i] = true;
                tmp.emplace_back(nums[i]);
                dfs(x+1, nums);
                tmp.pop_back();
                st[i] = false;
            }
        }
    }
};
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