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:
For example, given candidate set 2,3,6,7
and target 7
,
A solution set is:
[7]
[2, 2, 3]
思路:排序後,利用回溯去做,為了讓每個數都能重復,所以枚舉的時候可以在從這個數的下標開始一次
class Solution { public: void dfs(vectorcandidates, int index, int sum, int target, vector > &res, vector &path) { if (sum > target) return; if (sum == target) { res.push_back(path); return; } for (int i = index; i < candidates.size(); i++) { path.push_back(candidates[i]); dfs(candidates, i, sum+candidates[i], target, res, path); path.pop_back(); } } vector > combinationSum(vector &candidates, int target) { sort(candidates.begin(), candidates.end()); vector > res; vector path; dfs(candidates, 0, 0, target, res, path); return res; } };