40. Combination Sum II

Published on April 17, 2023

Question

Given a target and an array, find the combination that sum to target. An element should not be used twice.

Algorithm

So the elements could be duplicate thus generate duplicate results. We could sort the candidates first and skip them when doing backtracking.

The left things is much similar to question 39.

Code

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);
        helper(candidates, res, target, 0, 0, new ArrayList<>());
        return res;
    }
    
    private void helper(int[] candidates, List<List<Integer>> res, int target, int index, int sum, List<Integer> list) {
        if (sum == target) {
            res.add(new ArrayList<>(list));
        } else if (sum < target) {
            for (int i = index; i < candidates.length; i++) {
                if (i != index && candidates[i] == candidates[i-1]) continue;
                list.add(candidates[i]);
                helper(candidates, res, target, i + 1, sum + candidates[i], list);
                list.remove(list.size() - 1);
            }
        }
    }
}