Given a set of candidate numbers (C) (without duplicates) 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: 

1
2
3
4
[
  [7],
  [2, 2, 3]
]

思路

本题可以直接用回溯的方法来解决。

效率特别低……开了好多奇奇怪怪的东西

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 {
public:
    void combination(vector<int>& candidates, int target, set<vector<int>>& result, vector<int> tmp){
        if(target == 0){
            sort(tmp.begin(), tmp.end());
            result.insert(tmp);
            return;
        }
        else if(target < 0) return;
        for(int i = 0; i < candidates.size(); i++){
            vector<int> new_tmp(tmp);
            new_tmp.push_back(candidates[i]);
            combination(candidates, target-candidates[i], result, new_tmp);
        }
    }
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        set<vector<int>> result;
        vector<int> tmp;
        combination(candidates, target, result, tmp);
        vector<vector<int>> real_result;
        copy(result.begin(), result.end(), back_inserter(real_result));
        return real_result;
    }
};