请问该怎么理解李扣39、40这类题呢？

李扣39 combination sum，40 combination sum ii 看答案是用dfs+backtracking解答。想了好久仍感觉不好理解。请问该怎么样去理解这类题呢？有什么窍门吗？该怎么样去练习这样的思维呢？谢谢！

youtube搜basketwangcoding

建议自己根据代码手动模拟一下，比如数据量小一点，5个数一组，把递归函数分层画一下，什么时候返回上一层，返回之后需不需要reset之类的。我觉着记住这个图会方便理解代码。

模拟展开的过程就是一个解空间，换句话说就是所有解的可能
这个空间可以用树来表示，dfs+backtracking 就是在遍历这个解空间
如果当前这个节点不满足条件就backtracking，不再继续往下查找了

1. 其实最基础的思想还是遍历，遍历就需要用到 DFS。
2. 遍历也是有技巧的，不能不撞南墙不死心，及时设置条件触发回溯，相当于剪枝。
3. 别忘了先对原始数组排序。

39是无dup可复用， 40是有dup不可复复用
先说39
输入int[] nums, int target
我们可以把答案当成是数组的可复用的combination,也就是输出答案其实是 [x0,x1,x2,x3..xn-1] 满足 n0*x0+n1*x1+... == target
这个思路入手的话，下一个步就是怎样避免遍历多次，那么其实就可以吧这样的combination分解成如下的不同组
[1,*,*,*...], [2,*,*,....]...[x,*,*,.....]
[0,1,*,*....],[0,2,*,*,...]....[0,x,*,*,...]
[0,0,1,....]
[0,0,0,1,....]

同样的对于40，实际上40更简单，因为数字不能复用，你要找的其实就是[0,1,1,0,0,1....]这样的布尔组合， 同样的，可以把组合当成
[1,*,*,*...]
[0,1,*,*,...]
[0,0,1,*....]

当把组合都拆成这样互相肯定不会有overlap的组的时候，就很容易实现backtracking。下一步就是找剪枝条件。
那么对于这两题都是一样的，要么得到的组合刚好等于target，把组合加入答案，要么达到数组末尾，回退，那么小于target，回退，那么大于target，再进入下一层

还有一个，由于40的nums有dup，尽管可能的布尔组合是不同的，但是映射后的数字组合却相同，那么我们可以考虑增加一个限制条件，就是先把nums排序后，每一层在选择的时候，都选择不同的数字，使得映射后的组合依旧是唯一的。