首页 > 代码库 > leetcode 39. Combination Sum
leetcode 39. Combination Sum
类似 二叉树遍历到根节点path，也类似深度优先搜索
- 首先保持一个result的vector<vector>，是引用类型。
- 声明一个保持中间结果的vector，这个vector 始终在变化，在递归中使用
- 每次让target-candidates[i]，将candidate[i]加入temp中
- 如果target==0，满足条件将temp加入result 中
但是有两点要注意的：
- 每次同一个递归层上的temp 要不变，所以将push 进temp，之后要pop出来
- 因为不能有重复结果，但是每一个candidates又可以用多次，所以在大递归层上 ，如果考虑了candidates[1]，下次就要考虑candidates[2]. 但是在内部递归时，不需要从下一个节点开始:
class Solution { void comSum(vector<int> &candidates,vector<vector<int>> &result,int s, vector<int> temp, int target) { if(target==0) { result.push_back(temp); return; } for(int i=s;i<candidates.size();i++) { if(candidates[i]<=target) { temp.push_back(candidates[i]); cout<<candidates[i]<<endl; cout<<target<<endl; // int t=temp.size(); // temp[t]=candidates[i]; comSum(candidates, result,s, temp,target-candidates[i]); temp.pop_back(); } if(candidates[i]>target) return; s=s+1; } }public: vector<vector<int>> combinationSum(vector<int>& candidates, int target) { sort(candidates.begin(),candidates.end()); vector<vector<int>> result; vector<int> temp; comSum(candidates,result,0, temp, target); return result; }};
leetcode 39. Combination Sum
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。