Leetcode: Combination Sum II

Combination



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.

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

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])
                continue
            # 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:
                    res.append([candidates[i]]+element)

        return res
linkedin
github
slack

Share It, If You Like It.

Leave a Reply

Your email address will not be published.