05 August 2008
Given a set of candidate numbers (candidates) (without duplicates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target.
The same repeated number may be chosen from candidates unlimited number of times.
Note:
Example 1:
1
2
3
4
5
6
Input: candidates = [2,3,6,7], target = 7,
A solution set is:
[
[7],
[2,2,3]
]
Example 2:
1
2
3
4
5
6
7
Input: candidates = [2,3,5], target = 8,
A solution set is:
[
[2,2,2,2],
[2,3,3],
[3,5]
]
给一个没有重复元素的数组，找出里面的元素加起来等于target的所有组合，原数组的元素可以利用多次。这种求所有组合的情况通常都是另外写一个方法来做递归求得（这里是这类型题的总结）。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public List<List<Integer>> combinationSum(int[] candidates, int target) {
List<List<Integer>> results = new ArrayList<>();
if (candidates == null || candidates.length == 0) {
return results;
}
Arrays.sort(candidates);
dfs(candidates, results, new ArrayList<>(), target, 0, 0);
return results;
}
private void dfs(int[] candidates, List<List<Integer>> results, List<Integer> oneResult, int target, int sum, int index) {
if (sum == target) {
results.add(new ArrayList<>(oneResult));
}
if (sum > target) {
return;
}
for (int i = index; i < candidates.length; i++) {
oneResult.add(candidates[i]);
//下一轮还可以选本身，所以是i而非i+1,sum + candidates[i]作为参数而不是赋值
dfs(candidates, results, oneResult, target, sum + candidates[i], i); //下一轮是sum + candidates[i]，sum有变化
oneResult.remove(oneResult.size() - 1); //回溯
}
}
}