Combination Sum II

Question

https://leetcode.com/problems/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]
]

Tags

• Array
• Backtracking

Thought

This is still backtracking problem and we can use the recursion to track all the paths to get the correct answers.

Code

class Solution(object):
    def combinationSum2(self, candidates, target):
        """
        :type candidates: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        def helper(number, start, res, result, solution):
            if res == 0:
                result.append(solution)
                return
            for i in xrange(start, len(number)):
                if i > start and number[i] == number[i - 1]:
                    continue
                if number[i] > res:
                    break
                helper(number, i + 1, res - number[i], result, solution + [number[i]])

        result = []
        helper(sorted(candidates), 0, target, result, [])
        return result