题解 | 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;
    }
};
全部评论

相关推荐

评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务