四数之和问题18

Question

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38

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

加油！：）