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.
• 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.

解题方法

唯一差别就是每个数只能用一次，所以直接dfs recursive call的时候index + 1就可以了

Solution

class Solution(object):
    def combinationSum2(self, candidates, target):
        """
        :type candidates: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        results = []
        if not candidates:
            return [[]]
        candidates.sort()
        self.combHelper(results, candidates, target, 0, [])
        return results

    def combHelper(self, results, candidates, target, index, curList):
        if sum(curList) == target:
            tmpList = list(curList)
            results.append(tmpList)
        elif sum(curList) > target:
            return

        for i in range(index, len(candidates)):
            if i != index and candidates[i] == candidates[i-1]:
                continue
            curList.append(candidates[i])
            self.combHelper(results, candidates, target, i+1, curList)
            curList.pop()

Reference