四数之和问题18

Question

int getSum(vector<int> condidate){
    int total;
    for(int i=0;i<condidate.size();i++)
        total+=condidate[i];
    return total;
}

void dfs(vector<vector<int>>& ret,vector<int> condidate,vector<int>& nums,int curIndex,int target){
    if(condidate.size()==4){
        int total=getSum(condidate);
        if(total==target)
            ret.push_back(vector<int>(condidate));
        return;
    }
    //cout<<condidate.size()<<endl;
    if(curIndex>nums.size()-1)
        return;
    for(int i=curIndex;i<nums.size();i++){
        if(i!=curIndex&&nums[i]==nums[i-1])
            continue;
        condidate.push_back(nums[i]);
        if(getSum(condidate)>target&&nums[i]>0){
            if(!condidate.empty())
                condidate.pop_back();
            return;
        }
        dfs(ret,condidate,nums,i+1,target);
        if(!condidate.empty())
            condidate.pop_back();
    }
}

vector<vector<int>> fourSum(vector<int>& nums, int target) {
    sort(nums.begin(),nums.end());
    vector<vector<int>> ret;
    dfs(ret,vector<int>(),nums,0,target);
    return ret;
}

老师，这是我在网上看到的一个解决四数之和的算法，用的深度遍历的方法，用java实现的，然后我改写成了c++，但是在leetcode上执行，总是返回空

我调试了下，condidate.size都是小于4的，所以这句里面根本就不会执行，所以一直返回空

老师能帮我看下，我这个算法写的哪里有问题？

下面是我参考的算法的地址：https://blog.csdn.net/lm2009200/article/details/76184086

Answer 1

liuyubobobo 2018-08-31 11:16:59

这么小的测试用例，只有6个数字，自己调试一下，看看为什么condidate.size一直小于4？你遇到的这个问题，我怀疑直接使用4个数字的测试用例都能再现。仔细调试一下试试看？：）debug可是程序员的基本功哦，而且对于编写算法的深入理解，就在debug的过程中，进步就发生在这里哦：）

如果需要可以参考我的这个问题的参考代码：https://github.com/liuyubobobo/Play-Leetcode/tree/master/0018-4Sum/cpp-0018

加油！：）