Combination Sum II

Problem: Combination Sum II

It's a simple backtracking problem.

Code in Python:

class Solution(object):
    def combinationSum2(self, candidates, target):
        """
        :type candidates: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        candidates = sorted(candidates)
        n = len(candidates)

        res = []
        def helper(pos, _sum, combination):
            for i in xrange(pos, n):
                if i > pos and candidates[i] == candidates[i-1]: continue
                if _sum + candidates[i] < target: helper(i+1, _sum+candidates[i], combination+[candidates[i]])
                elif _sum + candidates[i] == target: res.append(combination+[candidates[i]])
                else: return
        helper(0, 0, [])
        return res

Code in Java:

public class Solution {
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        if (candidates.length == 0 || candidates == null) return null;

        Arrays.sort(candidates);
        List<List<Integer>> res = new ArrayList<>();
        helper(candidates, 0, new ArrayList<Integer>(), 0, target, res);
        return res;
    }

    private void helper(int[] candidates, int position, List<Integer> combination, int sum, int target, List<List<Integer>> res) {
        if (sum == target) {
            res.add(new ArrayList<>(combination));
            return;
        }

        for (int i = position; i < candidates.length; i++) {
            if (sum + candidates[i] > target) return;
            if (i > position && candidates[i] == candidates[i-1]) continue;
            combination.add(candidates[i]);
            helper(candidates, i+1, combination, sum+candidates[i], target, res);
            combination.remove(combination.size()-1);
        }
    }
}