组合总和

39. 组合总和

给定一个无重复元素的数组 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的数字可以无限制重复被选取。

说明:

所有数字(包括 target)都是正整数。
解集不能包含重复的组合。

今天的这题和昨天的基本一致,就连解法也没有过多差异。只不过这题的数字是可以重复的,所以我们传参时索引不必+1,然后在剪枝时,如果此时的总和已经大于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
class Solution {
public List<List<Integer>> combinationSum(int[] candidates, int target) {
List<List<Integer>> lists = new ArrayList<>();
List<Integer> list = new ArrayList<>();
backTrace(lists, candidates, list, 0, 0, target);
return lists;
}

private void backTrace(List<List<Integer>> lists, int[] candidates, List<Integer> list, int index, int sum, int target) {
if (sum == target) {
lists.add(new ArrayList<>(list));
}
if (sum > target) {
return;
}
for (int i = index; i < candidates.length; i++) {
list.add(candidates[i]);
sum += candidates[i];
backTrace(lists, candidates, list, i, sum, target);
list.remove(list.size() - 1);
sum -= candidates[i];
}
}
}