给你一个无重复元素的整数数组candidates和一个目标整数target,找出 candidates中可以使数字和为目标数 target的所有不同组合,并以列表形式返回,你可以按任意顺序 返回这些组合
candidates中的同一个数字可以无限制重复被选取,如果至少一个数字的被选数量不同则两种组合是不同的。
每次选取候选数组中的一位,默认第一位,递归选取该位以及后一位,避免重复递归,排序后使得算法更加优化
class Solution { public: vector<vector<int>> res; vector<int> temp; vector<vector<int>> combinationSum(vector<int>& candidates, int target) { sort(candidates.begin(),candidates.end());//排序为了减少递归 trackback(candidates,0,target);//从第一个数开始选 return res; } void trackback(vector<int>& candidates,int i,int target){ if(target==0){ res.push_back(temp);//满足条件记录 return; } for(;i<candidates.size();i++){ if(target>=candidates[i]){ temp.push_back(candidates[i]); trackback(candidates,i,target-candidates[i]);//递归下一次选取,往后选 temp.pop_back(); } else break;//不满足直接跳出循环,因为后面的更不满足 } } };