首页 > itarticle > combinationsum

combinationsum

admin 11月 12, 2020 0

Given a set of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

The same repeated number may be chosen from C unlimited number of times.

Note:

All numbers (including target) will be positive integers.
The solution set must not contain duplicate combinations.

For example, given candidate set [2, 3, 6, 7] and target 7,
A solution set is:

[ [7], [2, 2, 3]]

用回溯解决这个问题 非常方便，首先排序一下，然后每次判断一下是不是已经超过target值再进入下一层递归。

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
34
35
36
37
38
39
40
41
42
43
44
 
class Solution {
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        sort(candidates.begin(), candidates.end());
        vector<vector<int> > result;
        vector<int> tmp;
        __combinationSum(result, tmp, candidates, 0, target, 0);
        return result;
    }
    void __combinationSum(vector<vector<int> >& result, vector<int>& tmp, vector<int>& candidates, int sum, int target, int idx){
        if(sum == target){
            result.push_back(tmp);
            return;
        }
        for(int i = idx; i < candidates.size(); ++i){
            if(sum + candidates[i] > target) break;
            tmp.push_back(candidates[i]);
            __combinationSum(result, tmp, candidates, sum + candidates[i], target, i);
            tmp.pop_back();
        }
    }
};

当不允许重复的时候

Given a collection of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

Each number in C may only be used once in the combination.

Note:

All numbers (including target) will be positive integers.
The solution set must not contain duplicate combinations.

For example, given candidate set [10, 1, 2, 7, 6, 1, 5] and target 8,
A solution set is: [[1, 7],[1, 2, 5],[2, 6],[1, 1, 6]]

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
 
class Solution {
public:
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        sort(candidates.begin(), candidates.end());
        vector<vector<int> > result;
        vector<int> tmp;
        __combinationSum(result, tmp, candidates, 0, target, 0);
        return result;
    }
    void __combinationSum(vector<vector<int> >& result, vector<int>& tmp, vector<int>& candidates, int sum, int target, int idx){
        if(sum == target){
            result.push_back(tmp);
            return;
        }
        int i = idx;
        while( i < candidates.size()){
            if(sum + candidates[i] > target) break;
            tmp.push_back(candidates[i]);
            __combinationSum(result, tmp, candidates, sum + candidates[i], target, i + 1);
            tmp.pop_back();
            int value = candidates[i];
            while((i < candidates.size() && candidates[i] == value)){
                i++;
            }
        } 	
    }
};

最后套路一下，做回溯之前先对数组排序，这样可以获得一些顺序信息。

微海报分享

近期文章

近期评论

标签

热门

文章归档

分类目录

功能