Given a set of candidate numbers (candidates
) (without duplicates) and a target number (target
), find all unique combinations in candidates
where the candidate numbers sums to target
.
The same repeated number may be chosen from candidates
unlimited number of times.
Note:
- All numbers (including
target
) will be positive integers. - The solution set must not contain duplicate combinations.
Example 1:
Input: candidates =[2,3,6,7],
target =7
, A solution set is: [ [7], [2,2,3] ]
Example 2:
Input: candidates = [2,3,5],
target = 8,
A solution set is:
[
[2,2,2,2],
[2,3,3],
[3,5]
]
我的解答:
class Solution { public: vector<vector<int>> combinationSum(vector<int>& candidates, int target) { vector<vector<int>> res; vector<int> temp; //if (candidates.size() < 1)return res; sort(candidates.begin(),candidates.end()); combinationSum(candidates,res,temp,target,0); return res; } private: void combinationSum(vector<int>& candidates, vector<vector<int>> &res,vector<int> &temp, int target,int begin) { if (!target) { res.push_back(temp); return ; } // 这里要注意了,&& 两边应该先判断 i ,再判断candidates[i],否则将导致数组越界!!! for (int i = begin; i != candidates.size() && target >= candidates[i]; ++i) { temp.push_back(candidates[i]); combinationSum(candidates,res,temp,target - candidates[i],i); temp.pop_back(); } } };
其中有一个要注意的地方:
&& 运算符:先判断左边,只有左边为真,才计算右边
|| 运算符:先判断左边,只有左边为假,才计算右边