39.组合总和

一开始我们很容易就写出一个合规，但是存在多余结果的一个版本
对于num上的数，做出一个dfs函数, 只要在每一层遍历数组，同时将可以减到left的结果压到res数组中。

但是这样，可能会出现重复的选择。即相邻递归层之间的数值互换的情况。

class Solution {
    vector<vector<int>> res_;
    vector<int> tmp_;
public:

    void helper(vector<int>& candidates, int left) {
        if(left == 0) {
            res_.push_back(tmp_);
            return;
        }else if(left < 0){
            return;
        }

        for(auto num : candidates) {
            tmp_.push_back(num);
            helper(candidates, left - num);
            tmp_.pop_back();
        }
    }

    vector<vector<int>> 
    combinationSum(vector<int>& candidates, int target) {
        helper(candidates, target);
        return std::move(res_);
    }
};
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

通过观察，我们发现，如果num < tmp.back()， 说明我们已经重复选择了。因此，只要把该条件加上即可。

class Solution {
    vector<vector<int>> res_;
    vector<int> tmp_;
public:

    void helper(vector<int>& candidates, int left) {
        if(left == 0) {
            res_.push_back(tmp_);
            return;
        }else if(left < 0){
            return;
        }

        for(auto num : candidates) {
            // 此处用去重
            if(tmp_.size() != 0 && tmp_.back() > num) {
                continue;
            }

            tmp_.push_back(num);
            helper(candidates, left - num);
            tmp_.pop_back();
        }
    }

    vector<vector<int>> 
    combinationSum(vector<int>& candidates, int target) {
        helper(candidates, target);
        return std::move(res_);
    }
};
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

但是，再观察可以得出一个结果，就是每次递归的所选的正确的下标，总是$>=$上一个下标(即tmp.back())， 因此，我们可以通过在递归函数中，传递下标，来减少迭代次数。

class Solution {
    vector<vector<int>> res_;
    vector<int> tmp_;
public:

    void helper(vector<int>& candidates, int idx, int left) {
        if(left == 0) {
            res_.push_back(tmp_);
            return;
        }else if(left < 0){
            return;
        }

        for(int i = idx; i != candidates.size(); ++i) {
            int num = candidates[i];
            tmp_.push_back(num);
            helper(candidates, i, left - num);
            tmp_.pop_back();
        }
    }

    vector<vector<int>> 
    combinationSum(vector<int>& candidates, int target) {
        helper(candidates, 0, target);
        return std::move(res_);
    }
};
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

40. 组合总和 II

这个与39没多大区别，只是数组中的数不再是无限的，而只能用一次。

同时，由于数组的输入不是唯一的，可能还会存在重复的数。因此，我们需要做一个排序，使得相同的数都相邻(有没有三数之和的味道?), 然后在选数时加个判断，如果前一个数，跟当前数相同，那么一定已经选过了，我们需要剪枝。

class Solution {
    vector<vector<int>> res_;
    vector<int> tmp_;
public:

    void helper(vector<int>& candidates, int idx, int left) {
        if(left == 0) {
            res_.push_back(tmp_);
            return;
        }else if(left < 0){
            return;
        }

        for(int i = idx; i != candidates.size(); ++i) {
            if(i != idx && candidates[i] == candidates[i-1]) continue;
            int num = candidates[i];
            tmp_.push_back(num);
            
            // 改成 i + 1, 实现了数只能用一次.
            helper(candidates, i + 1, left - num);
            tmp_.pop_back();
        }
    }

    vector<vector<int>> 
    combinationSum2(vector<int>& candidates, int target) {
        sort(candidates.begin(), candidates.end());
        helper(candidates, 0, target);
        return std::move(res_);
    }
};
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

---

46. 全排列

class Solution {
    vector<int>         tmp_;      
    vector<bool>        isVisited_; // Note: 状态数组
    vector<vector<int>> res_;
public:
    
    void helper(const vector<int>& nums){
        if(nums.size() == tmp_.size()){
            res_.push_back(tmp_);
            return;
        }

        for(int i = 0; i != isVisited_.size(); ++i) {
            if (isVisited_[i]  == true) continue;
            isVisited_[i] = true;
            tmp_.push_back(nums[i]);
            helper(nums);
            tmp_.pop_back();
            isVisited_[i] = false;
        }
    }

    vector<vector<int>> permute(vector<int>& nums) {
        isVisited_.assign(nums.size(), false); 
        helper(nums);
        return res_;
    }
};
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

---

*47. 全排列 II

现在变成了排列问题，同时允许重复。单纯换了一下条件

首先我们需要排一下序使得重复的数字都相邻。然后在选取条件时，需要比较注意。如果前一个相同的数没被选，这意味着前一个数已经被选过了，因此我们需要跳过当前的这个数。

class Solution {
    vector<vector<int>> res;
    vector<int>         tmp;
    vector<bool>  isVisited;
public:
    void helper(vector<int>& nums, int curIdx){
        if(nums.size() == curIdx) {
            res.push_back(tmp);
            return;
        }

        for(int i = 0; i != nums.size(); i++) {
            if(isVisited[i] == true 
            || i > 0 && nums[i-1] == nums[i] && !isVisited[i-1]) continue;
            
            isVisited[i] = true;

            tmp.push_back(nums[i]);
            helper(nums, curIdx + 1);
            tmp.pop_back();

            isVisited[i] = false;
        }
    }
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        isVisited.assign(nums.size(), false);
        helper(nums, 0);
        return res;
    }
};
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

---

78. 子集

class Solution {
public:
    
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> bkt;

        
        bkt.push_back(vector<int>());
        for(int i = 0; i != nums.size(); ++i) {
            int len = bkt.size();
            for(int j = 0; j != len; ++j){
                vector<int> tmp;
                tmp.assign()

                tmp.push_back(nums[i]);

                bkt.push_back(tmp);
            }
        }

        return bkt;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

剑指 Offer II 079. 所有子集

与78. 子集是一样的，这里提供另一个思路，从子集的概念出发。

思路: 根据子集的思路，对每个元素，要么选，要么不选。

通过二进制位来标识选择

class Solution {
public:

    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> res;
        int len = nums.size();

        // bits: 二进制位的不同状态个数
        // Note: 位运算的优先级问题
        for(int bits = 0; bits <= (1 << len) - 1; ++bits) {
            vector<int> tmp;

            for(int i = 0; i != len; i++){
                if( ((1 << i) & bits) != 0) {
                    tmp.push_back(nums[i]);
                }
            }

            res.push_back(tmp);
        }


        return res;
    }
};
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

用递归函数思路更简洁

class Solution {
    vector<vector<int>> res;
    vector<int>         tmp;

public:
    void helper(const vector<int>& nums, int curidx) {
        if(curidx == nums.size()) {
            res.push_back(tmp);
            return;
        }

        // 不选
        helper(nums, curidx + 1);

        // 选
        tmp.push_back(nums[curidx]);
        helper(nums, curidx + 1);
        tmp.pop_back();
    }

    vector<vector<int>> subsets(vector<int>& nums) {
        helper(nums, 0);
        return res;
    }
};
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

90. 子集 II