代码：
个人浅薄的认为DFS就是回溯法中的一种，一般想到用DFS我们脑中一般都有一颗解法树，然后去按照深度优先搜索去寻找解。而分支界限法则不算是回溯，无论其是采用队列形式的还是优先队列形式的分支界限法。
下面这个函数就是我的DFS的函数，先介绍一下参数的含义，index表示当前要判断是否合适的candidates中的元素的下标，t表示即将要把新数据加入的位置。
1 void backTrace(int sum, int target, int a[], int index, int t, vector & candidates) 2 { 3 if (sum == target) 4 { 5 vector b; 6 for (int i = 0; i < t; i++) 7 { 8 b.push_back(a[i]); 9 }10 sort(b.begin(),b.end());11 result.push_back(b);12 }13 if (sum>target)14 {15 return;16 }17 for (int i = index; i < candidates.size(); i++)18 {19 a[t] = candidates[i];20 backTrace(sum + candidates[i], target, a, i, t + 1, candidates);21 }22 } 这是很典型的深搜的题目了，我写回溯法特别容易出错，一个好的解决方法就是画出简易的、局部的解法树，然后根据解法树判断什么时候回溯，回溯的下一步是什么，回溯的逻辑关系是循环控制还是有其他方式控制（二叉树就是简单的左右控制），还有就是当前参数就是当前的数据源不能混。
哈哈哈哈！！！
这个题我也有改进技巧啦：
1 #include2 #include 3 #include 4 5 using namespace std; 6 7 8 vector > result; 9 int a[100];10 11 void backTrace(int sum, int target, int a[], int index, int t, vector & candidates)12 {13 if (sum == target)14 {15 vector b;16 for (int i = 0; i < t; i++)17 {18 b.push_back(a[i]);19 }20 result.push_back(b);21 }22 if (sum>target)23 {24 return;25 }26 for (int i = index; i < candidates.size(); i++)27 {28 a[t] = candidates[i];29 backTrace(sum + candidates[i], target, a, i, t + 1, candidates);30 if (candidates[i] + sum > target)31 return;32 }33 }34 35 vector > combinationSum(vector & candidates, int target)36 {37 sort(candidates.begin(), candidates.end());38 backTrace(0, target, a, 0, 0, candidates);39 return result;40 }41 42 int main()43 {44 vector can = { 2, 3, 6, 7 };45 combinationSum(can, 7);46 for (int i = 0; i < result.size(); i++)47 {48 for (int j = 0; j < result[i].size(); j++)49 {50 cout << result[i][j] << " ";51 }52 cout << endl;53 }54 }
改进点就是先对candidates进行从小到大的排序，然后就可以加上30~31的这行代码了，这个能减少不少无用的尝试，然后就是结果集，由于我们已经排好序了，且加入是从小到大所以，后来的就不需要排序了，直接添加就好了。少了第10行。
哈哈哈哈哈哈。。。。
我的一个小伙伴提供了一个思路，根据这个思路可以不用recursion，下面介绍一下，明天叫上代码：
先用target去减集合中的第一个元素然后在集合中寻找减的结果，如果有则作为一个成功的探索，如果没有继续减该元素然后继续寻找，直到减的结果小于零。再去尝试集合中的下一个元素。