题目描述
给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。 candidates 中的数字可以无限制重复被选取。
解题思路
1、关键点在于，如何判断数字和为 target，设置变量remain来记录是否为target
remain
- nums
[i
]
代码
class Solution {
public List
<List
<Integer>> combinationSum(int[] candidates
, int target
) {
List
<List
<Integer>> list
= new ArrayList<>();
Arrays
.sort(candidates
);
backtrack(list
, new ArrayList<>(),candidates
, target
, 0);
return list
;
}
private void backtrack(List
<List
<Integer>> list
, List
<Integer> templist
, int[] nums
, int remain
, int start
){
if(remain
< 0) return;
else if(remain
== 0) list
.add(new ArrayList<>(templist
));
else{
for(int i
= start
; i
< nums
.length
; i
++){
templist
.add(nums
[i
]);
backtrack(list
, templist
, nums
, remain
- nums
[i
], i
);
templist
.remove(templist
.size() - 1);
}
}
}
}
参考：https://leetcode.com/problems/subsets/discuss/27281/A-general-approach-to-backtracking-questions-in-Java-(Subsets-Permutations-Combination-Sum-Palindrome-Partitioning)
