leetcode_39 组合总和

1. 题意

给定一个数组，和一个目标值；求得所有数组中所有和为目标值的元素序列。

组合总数

2. 题解

回溯列举每一个可能的序列，注意去重。

2.1 我的解法

class Solution {
public:
    void gen(vector<vector<int>> &ans,const vector<int> &candidates, vector<int> &seq, int target)
    {
        if (target == 0) {
            ans.push_back(seq);
            return ;
        }
        if ( target < 0)
            return ;

        int sz = candidates.size();
        for ( int i = 0; i < sz; ++i) {
            if ( !seq.empty() &&candidates[i] < seq[seq.size() - 1])
                continue;
            
            seq.push_back(candidates[i]);
            gen(ans, candidates, seq, target - candidates[i]);
            seq.pop_back();
        }
    }


    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        
        vector<vector<int>> ans;
        vector<int> one;
        sort(candidates.begin(), candidates.end());
        gen(ans, candidates, one, target);

        return ans;
    }
};
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
33

2.2 另一种可能

class Solution {
public:
    void gen(vector<vector<int>> &ans,const vector<int> &candidates, vector<int> &seq, 
        int idx, int target)
    {
        if (target == 0) {
            ans.push_back(seq);
            return ;
        }
        if ( target < 0)
            return ;

        int sz = candidates.size();
        for ( int i = idx; i < sz; ++i) {
            
            
            seq.push_back(candidates[i]);
            gen(ans, candidates, seq, i, target - candidates[i]);
            seq.pop_back();
        }
    }


    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        
        vector<vector<int>> ans;
        vector<int> one;
        sort(candidates.begin(), candidates.end());
        gen(ans, candidates, one, 0, target);

        return ans;
    }
};
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
33