回溯法和DFS leetcode Combination Sum

代码：

个人浅薄的认为DFS就是回溯法中的一种，一般想到用DFS我们脑中一般都有一颗解法树，然后去按照深度优先搜索去寻找解。而分支界限法则不算是回溯，无论其是采用队列形式的还是优先队列形式的分支界限法。

下面这个函数就是我的DFS的函数，先介绍一下参数的含义，index表示当前要判断是否合适的candidates中的元素的下标，t表示即将要把新数据加入的位置。

 void backTrace(int sum, int target, int a[], int index, int t, vector<int>& candidates)

 {

     if (sum == target)

     {

         vector<int> b;

         for (int i = ; i < t; i++)

         {

             b.push_back(a[i]);

         }

         sort(b.begin(),b.end());

         result.push_back(b);

     }

     if (sum>target)

     {

         return;

     }

     for (int i = index; i < candidates.size(); i++)

     {

         a[t] = candidates[i];

         backTrace(sum + candidates[i], target, a, i, t + , candidates);

     }

 }

这是很典型的深搜的题目了，我写回溯法特别容易出错，一个好的解决方法就是画出简易的、局部的解法树，然后根据解法树判断什么时候回溯，回溯的下一步是什么，回溯的逻辑关系是循环控制还是有其他方式控制（二叉树就是简单的左右控制），还有就是当前参数就是当前的数据源不能混。

哈哈哈哈！！！

这个题我也有改进技巧啦：

 #include<iostream>

 #include<vector>

 #include<algorithm>

 using namespace std;

 vector<vector<int>> result;

 int a[];

 void backTrace(int sum, int target, int a[], int index, int t, vector<int>& candidates)

 {

     if (sum == target)

     {

         vector<int> b;

         for (int i = ; i < t; i++)

         {

             b.push_back(a[i]);

         }

         result.push_back(b);

     }

     if (sum>target)

     {

         return;

     }

     for (int i = index; i < candidates.size(); i++)

     {

         a[t] = candidates[i];

         backTrace(sum + candidates[i], target, a, i, t + , candidates);

         if (candidates[i] + sum > target)

             return;

     }

 }

 vector<vector<int>> combinationSum(vector<int>& candidates, int target)

 {

     sort(candidates.begin(), candidates.end());

     backTrace(, target, a, , , candidates);

     return result;

 }

 int main()

 {

     vector<int> can = { , , ,  };

     combinationSum(can, );

     for (int i = ; i < result.size(); i++)

     {

         for (int j = ; j < result[i].size(); j++)

         {

             cout << result[i][j] << "    ";

         }

         cout << endl;

     }

 }

改进点就是先对candidates进行从小到大的排序，然后就可以加上30~31的这行代码了，这个能减少不少无用的尝试，然后就是结果集，由于我们已经排好序了，且加入是从小到大所以，后来的就不需要排序了，直接添加就好了。少了第10行。

哈哈哈哈哈哈。。。。

我的一个小伙伴提供了一个思路，根据这个思路可以不用recursion，下面介绍一下，明天叫上代码：

先用target去减集合中的第一个元素然后在集合中寻找减的结果，如果有则作为一个成功的探索，如果没有继续减该元素然后继续寻找，直到减的结果小于零。再去尝试集合中的下一个元素。

巴特西

回溯法和DFS leetcode Combination Sum

最新文章

热门文章