题目
给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的数字可以无限制重复被选取。
说明：
- 所有数字（包括 target）都是正整数。
- 解集不能包含重复的组合。
示例 1:
输入: candidates = [2,3,6,7], target = 7,
所求解集为:
[
[7],
[2,2,3]
]
示例 2:
输入: candidates = [2,3,5], target = 8,
所求解集为:
[
[2,2,2,2],
[2,3,3],
[3,5]
]
解题思路
关键是结束条件，每次遍历target-candidates[I]，传入下一个递归，如何等于0 ，结束，如果小于最小值也结束
深度遍历，可以重复，如果返回，则删除最后一位添加的，继续下一个的计算
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
26
27
28
29
30
31
32
33
| class Solution {
List list;
List item;
public List<List<Integer>> combinationSum(int[] candidates, int target) {
list = new ArrayList<>();
item = new ArrayList<Integer>();
if(candidates == null || candidates.length == 0){
return list;
}
Arrays.sort(candidates);
backTracing(0,candidates,target);
return list;
}
private void backTracing(int index ,int[] candidates , int target){
if(target == 0){
list.add(new ArrayList<>(item));
return;
}
if(target < candidates[0]){
return;
}
for(int i = index ; i< candidates.length ; i++){
int targetDelete = target - candidates[i];
item.add(candidates[i]);
backTracing(i, candidates, targetDelete);
item.remove(item.size()-1);
}
}
}
|
