专题四：综合练习（组合总和的暴搜dfs）

以leetcode39题为例

题目解析： 

给一个数组，然后可以无限制的使用里面的数字，选一些数全部加起来，如果等于target就是一种

算法原理分析： 

1.画决策树：越详细越好

代码设计：

1.全局变量：需要返回vector<vector<int>>所以我们设计一个vector<vector<int>>ret

                     需要一个path，当结点的和等于target时我们就放入ret中

                     int sum,用于计算path中的总和

                     int target，用于比较是否到达总和

2.dfs函数：从前往后枚举数组中的每一个元素

3.细节：回溯：每次恢复现场都要pop一下才进入下一个，并且path也要处理一下

              剪枝：只需要path+candidate[i]是否大于总和，大于就剪掉，也就是不选

             递归出口：当发现path==target时就return

代码编写：

 

这里注意：要去重，也就是3，2和2，3的组合一样

我在前面选2的时候已经考虑过2，3了

所以在接下来到罗列3的时候，不要在从2开始罗列，要从3，3开始罗列