Combination Sum II

Question

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.

Example For example, given candidate set 10,1,6,7,2,1,5 and target 8,

A solution set is:

[1,7]

[1,2,5]

[2,6]

[1,1,6]

Note All numbers (including target) will be positive integers. Elements in a combination (a1, a2, … , ak)`` must be in non-descending order.(ie, a1 ≤ a2 ≤ … ≤ ak)`. The solution set must not contain duplicate combinations.

Thoughts

跟I类似，但是会超时，所以要在sum已经larger than target的时候跳过接下来的list省去很多不必要的计算

Solution

class Solution:    
    """
    @param candidates: Given the candidate numbers
    @param target: Given the target number
    @return: All the combinations that sum to target
    """
    def combinationSum2(self, candidates, target): 
        # write your code here
        if not candidates:
            return []
        if not target:
            return []
        self.resultList = []
        self.S = candidates
        self.S.sort()
        self.target = target
        self.subsetsHelper([], 0)
        return self.resultList

    def subsetsHelper(self, curList, pos):
        if sum(curList) == self.target:
            newList = list(curList)
            self.resultList.append(newList)
        #if it's already larger than target, no need to calculate later results
        if sum(curList) > self.target:
            return 
        for i in range(pos, len(self.S)):
            if i != pos and self.S[i-1] == self.S[i]:
                continue
            curList.append(self.S[i])
            self.subsetsHelper(curList, i + 1)
            curList.pop()