题解 | NC46 加起来和为目标值的组合
二叉树根节点到叶子节点和为指定值的路径
http://www.nowcoder.com/practice/840dd2dc4fbd4b2199cd48f2dadf930a
题目
解法:先对原数组排序,利用树的深度遍历思想进行dfs,当target减为0时push到res中,去重的方法是在dfs过程中判断相邻数字是否相同if(i>index && num[i]==num[i-1])continue;如果前后数字相同则跳过
class Solution { public: vector<vector<int> > combinationSum2(vector<int> &num, int target) { vector<int>tmp; vector<vector<int>>res; sort(num.begin(),num.end()); dfs(num,target,0,tmp,res); return res; } void dfs(vector<int> &num,int target,int index,vector<int>& tmp,vector<vector<int>>& res) { //target:剩余值 index:起始数组元素下标 tmp存放一组结果 res存放所有组合 if(target<=0) { if(target==0)res.push_back(tmp); return; } for(int i=index;i<num.size();i++) { if(i>index && num[i]==num[i-1])continue; tmp.push_back(num[i]); dfs(num,target-num[i],i+1,tmp,res);//i+1从下一个元素开始 tmp.pop_back();//去除最后一个元素 } return; } };