Leetcodes Solution 39 Combination Sum

zhuanlan.zhihu.com

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,

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

思路1

利用backtracking，也就是簡粗暴的試錯辦法。

遍歷給定的candidates，然後用target減去當前candidates的值，再用剩下的數比較。不行就pop_back出來.

如果target被減成0了，說明當前的combination符合要求，放入res中。

class Solution{public: vector<vector<int>> combinationSum(vector<int>& candidates, int target){ sort(candidates.begin(), candidates.end()); vector<vector<int>> res; vector<int> combination; combinationSum(candidates, target, res, combination, 0); return res; }private: void combinationSum(vector<int> &candidates, int target, vector<vector<int>> &res, vector<int> &combination, int begin){ if(!target){ res.push_back(combination); return ; } for(int i = begin; i != candidates.size() && target >= candidates[i]; i++){ combination.push_back(candidates[i]); combinationSum(candidates, target - candidates[i], res, combination, i); combination.pop_back(); } }};

推薦閱讀：