题目描述（中等难度）

给几个数字，一个目标值，输出所有和等于目标值的组合。

解法一 回溯法

参考) ，就是先向前列举所有情况，得到一个解或者走不通的时候就回溯。和37题有异曲同工之处，也算是回溯法很典型的应用，直接看代码吧。

时间复杂度：

空间复杂度：

解法二 动态规划

参考。动态规划的关键就是找到递进关系，看到了下边的评论想通的。

我们用一个 opt 的 list，然后依次求出 opt [ 0 ]，opt [ 1 ] … opt [ target ]。

opt[0]，表示和为 0 的所有情况的组合。

opt[1]，表示和为 1 的所有情况的组合。

opt[2]，表示和为 2 的所有情况的组合。

…

opt[target]，表示和为 target 的所有情况的组合，也就是题目所要求的。

递进关系就是，sum 代表要求的和，如果想求 opt [ sum ] ，就遍历给定的数组 nums，然后分两种情况。

• 如果 sum 大于 nums [ i ]，那么我们就把 opt [ sum - nums [ i ] ] 的所有情况都加上 nums [ i ] 然后作为 opt [ sum ] 。

  例如 nums = [ 1, 2, 3, 6, 7 ] , target = 7。

  当 sum 等于 5 的时候，也就是求 opt [ 5 ] 的时候，此时当遍历到 nums [ 1 ]，此时 nums [ 1 ] = 2 < sum。然后，就看 opt [ sum - nums [ i ] ] = opt [ 5 - 2 ] = opt [ 3 ]，而 opt [ 3 ] 在之前已经求好了，opt [ 3 ] = [ [ 1, 2 ], [ 3 ] ]，然后把 opt [ 3 ] 中的每一种情况都加上 nums [ 1 ] ，也就是 2，就变成了 [ [ 1, 2, 2 ], [ 3, 2 ] ]，这个就是遍历到 nums [ 1 ] 时候的 opt [ 5 ]了。

上边的想法看起来没什么问题，但跑了下遇到一个问题。

比如求 nums = [ 2, 3, 6, 7 ] , target = 7 的时候。

求 opt [ 5 ]，然后遍历到 nums [ 0 ] = 2 的时候，就把 opt [ 3 ] = [ [ 3 ] ] 的所有情况加上 2，也就是[ 3 2 ] 加到 opt [ 5 ] 上。接着遍历到 nums [ 2 ] = 3 的时候，就把 opt [ 2 ] = [ [ 2 ] ] 的所有情况加上 3，然后 [ 2 3 ] 这种情况加到 opt [ 5 ] 上，此时 opt [ 5 ] = [ [ 3 2]，[ 2 3 ] ]。这样出现了重复的情况，需要解决一下。

这样就相当于二维数组去重，也就是 [ [ 3 2 ]，[ 2 3 ] , [ 1 ] ] 这样的列表去重变成 [ [ 2 3 ] , [ 1 ] ] 。最普通的想法就是两个 for 循环然后一个一个比对，把重复的去掉。但这样实在是太麻烦了，因为比对的时候又要比对列表是否相等，比对列表是否相等又比较麻烦。

这里看到一个方法，就是把每个 list 转成 string，然后利用 HashMap 的 key 是唯一的，把每个 list 当做 key 加入到 HashMap 中，这样就实现了去重，然后再把 string 还原为 list。

然后结合去重的方法，我们的问题就解决了。

时间复杂度：

空间复杂度：

还有另一种思路可以解决重复的问题。

之前对于 nums = [ 2, 3, 6, 7 ] , target = 7 ，我们用了两层 for 循环，分别对 opt 和 nums 进行遍历。

我们先求 opt [ 0 ]，通过遍历 nums [ 0 ]， nums [ 1 ]， nums [ 2 ]， nums [ 3 ]

然后再求 opt [ 1 ]，通过遍历 nums [ 0 ]， nums [ 1 ]， nums [ 2 ]， nums [ 3 ]

…

最后再求 opt [ 7 ]，通过遍历 nums [ 0 ]， nums [ 1 ]， nums [ 2 ]， nums [ 3 ]。

求 opt [ 5 ] 的时候，出现了 [ 2 3 ]，[ 3 2 ] 这样重复的情况。

我们可以把两个 for 循环的遍历颠倒一下，外层遍历 nums，内层遍历 opt。

考虑 nums [ 0 ]，求出 opt [ 0 ]，求出 opt [ 1 ]，求出 opt [ 2 ]，求出 opt [ 3 ] … 求出 opt [ 7 ]。

考虑 nums [ 1 ]，求出 opt [ 0 ]，求出 opt [ 1 ]，求出 opt [ 2 ]，求出 opt [ 3 ] … 求出 opt [ 7 ]。

考虑 nums [ 2 ]，求出 opt [ 0 ]，求出 opt [ 1 ]，求出 opt [ 2 ]，求出 opt [ 3 ] … 求出 opt [ 7 ]。

考虑 nums [ 3 ]，求出 opt [ 0 ]，求出 opt [ 1 ]，求出 opt [ 2 ]，求出 opt [ 3 ] … 求出 opt [ 7 ]。

这样的话，每次循环会更新一次 opt [ 7 ]，最后次更新的 opt [ 7 ] 就是我们想要的了。

这样之前的问题，求 opt [ 5 ] 的时候，出现了 [ 2 3 ]，[ 3 2 ] 这样重复的情况就不会出现了，因为当考虑 nums [ 2 ] 的时候，opt [ 3 ] 里边还没有加入 [ 3 ] 。

思路就是上边说的了，但是写代码的时候遇到不少坑，大家也可以先尝试写一下。

总

对回溯法又有了更深的了解，一般的架构就是一个大的 for 循环，然后先 add，接着利用递归进行向前遍历，然后再 remove ，继续循环。而解法二的动态规划就是一定要找到递进的规则，开始的时候就想偏了，导致迟迟想不出来。

添加好友一起进步~

如果觉得有帮助的话，可以点击 给一个 star 哦 ^^