经典组合题目,DFS。
class Solution {
public List<List<Integer>> combinationSum(int[] candidates, int target) {
List<List<Integer>> res = new ArrayList<>();
if (candidates == null || candidates.length == 0) {
return res;
}
Arrays.sort(candidates);
List<Integer> cur = new ArrayList<>();
helper(candidates, target, 0, cur, res);
return res;
}
private void helper(int[] candidates, int target, int index, List<Integer> cur, List<List<Integer>> res) {
if (getSum(cur) > target) {
return;
}
if (getSum(cur) == target) {
res.add(new ArrayList<>(cur));
return;
}
// 从 index 开始取,保证取到的下一位不小于当前位,避免结果出现 [2,2,3] 和 [2,3,2] 的重复
for (int i = index; i < candidates.length; i++) {
cur.add(candidates[i]);
// 可以取重复元素,所以这里传 i,而不是 i + 1
helper(candidates, target, i, cur, res);
cur.remove(cur.size() - 1);
}
}
private int getSum(List<Integer> list) {
int sum = 0;
for (int i = 0; i < list.size(); i++) {
sum += list.get(i);
}
return sum;
}
}