还是组合,DFS。参考 39. Combination Sum
class Solution {
public List<List<Integer>> combinationSum2(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;
}
for (int i = index; i < candidates.length; i++) {
// 很重要的去重
if (i != index && candidates[i] == candidates[i - 1]) {
continue;
}
cur.add(candidates[i]);
helper(candidates, target, i + 1, cur, res); // 这里传 i + 1,从 i + 1 开始取,避免一个值取多次
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;
}
}