[Leetcode] Combination sum II

Given a collection of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

Each number in C may only be used once in the combination.

Note:

• All numbers (including target) will be positive integers.
• The solution set must not contain duplicate combinations.

For example, given candidate set [10, 1, 2, 7, 6, 1, 5] and target 8,
A solution set is: 

[
  [1, 7],
  [1, 2, 5],
  [2, 6],
  [1, 1, 6]
]

This is not a hard problem - it's quite standard to think a recursion solution. However, the recursion solution sometimes doesn't work as I expected - it turns out the "exit" condition is quite important.

One little aspect: when there is repeated elements and order doesn't matter, sort always helps to remove the duplicates.

class Solution(object):
    def combinationSum2(self, candidates, target):
        """
        :type candidates: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        res = []
        candidates.sort()
        res = self.helper(candidates, target)
        return res
    
    def helper(self, candidates, target):
        if len(candidates) == 0: return []
        output = []
        for i, can in enumerate(candidates):
            if can > target: continue
            if i > 0 and can == candidates[i-1]: continue
            tmp_res = self.helper(candidates[i+1: ], target-can)
            if len(tmp_res) > 0:
                for tr in tmp_res:
                    output.append(tr+[can])
            if len(tmp_res) == 0: # important to determine if there is a solution or not
                if can == target:
                    output.append([can])
        return output