39. Combination Sum

Given an array of distinct integers candidates and a target integer target, return a list of all unique combinations of candidates where the chosen numbers sum to target. You may return the combinations in any order.

The same number may be chosen from candidates an unlimited number of times. Two combinations are unique if the frequency of at least one of the chosen numbers is different.

The test cases are generated such that the number of unique combinations that sum up to target is less than 150 combinations for the given input.

Example 1:

Input: candidates = [2,3,6,7], target = 7
Output: [[2,2,3],[7]]
Explanation:
2 and 3 are candidates, and 2 + 2 + 3 = 7. Note that 2 can be used multiple times.
7 is a candidate, and 7 = 7.
These are the only two combinations.

Example 2:

Input: candidates = [2,3,5], target = 8
Output: [[2,2,2,2],[2,3,3],[3,5]]

Example 3:

Input: candidates = [2], target = 1
Output: []

Constraints:

• 1 <= candidates.length <= 30
• 2 <= candidates[i] <= 40
• All elements of candidates are distinct.
• 1 <= target <= 40

方法一：递归
使用递归解法，这个递归方法是，依次遍历每个元素，判断其与剩余数字的大小，如果比剩余target小，那么就放入到路径path中，并且，把剩余元素target减去当前元素。

理解递归最重要的当然是递归函数的定义：以index为起始元素，在candidates的index元素和其之后的元素中，抽取一定的元素，能否构成和为target的路径Path。

Python代码如下：

class Solution(object):
def combinationSum(self, candidates, target):
“””
:type candidates: List[int]
:type target: int
:rtype: List[List[int]]
“””
res = []
candidates.sort()
self.dfs(candidates, target, 0, res, [])
return res

def dfs(self, nums, target, index, res, path):
if target < 0:
return
elif target == 0:
res.append(path)
return
for i in xrange(index, len(nums)):
if nums[index] > target:
return
self.dfs(nums, target – nums[i], i, res, path + [nums[i]])
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
方法二：回溯法
上面的DFS虽说也是递归，但是和回溯还是有区别的。因为回溯的含义，此路不通就倒着走回去，而上面的DFS是进行了全集的搜索。

这个回溯还是很好写的，需要一个新的函数，含义是从候选集的start位置开始向后寻找和为target的路径。如果target等于０了就是我们终止的一个条件，即正好搜索到了一条合适的路径。

需要注意的是path后面的插入元素和弹出元素操作。向path中添加元素i后进行后面的搜索，搜索完之后说明i位置的所有结果都已经结束了，故向后退一步即弹出最后的元素。

另外就是题目允许每个数字使用多次，所以for循环开始的地方是start，而往回溯函数里面传递的i的也是start.

C++代码如下：

class Solution {
public:
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
vector<vector<int>> res;
vector<int> path;
helper(candidates, 0, res, path, target);
return res;
}
void helper(vector<int>& candidates, int start, vector<vector<int>>& res, vector<int>& path, int target) {
if (target < 0) return;
if (target == 0) {
res.push_back(path);
}
for (int i = start; i < candidates.size(); ++i) {
path.push_back(candidates[i]);
helper(candidates, i, res, path, target – candidates[i]);
path.pop_back();
}
}
};
原文链接：https://blog.csdn.net/fuxuemingzhu/article/details/79322462