Leetcode: Combination Sum II


Similar Problems:

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.


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

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.

## Blog link: https://code.dennyzhang.com/combination-sum-ii
## Basic Ideas: Sort the list with descending order
## Complexity: Time O(n*n), Space O(n)
class Solution:
    def combinationSum2(self, candidates, target):
        :type candidates: List[int]
        :type target: int
        :rtype: List[List[int]]
        if len(candidates) == 0: return []
        candidates = sorted(candidates)
        length = len(candidates)
        res = []
        for i in range(length):
            if candidates[i] > target: continue
            if candidates[i] == target:
                if [target] not in res: res.append([target])
            # try to start the result with candidates[i]
            l = self.combinationSum2(candidates[i+1:], target - candidates[i])
            for element in l:
                if not [candidates[i]]+element in res:

        return res

Share It, If You Like It.

Leave a Reply

Your email address will not be published.