menu

[LeetCode] 040. Combination Sum II

Problem (Medium)

040. Combination Sum II

Given a collection of candidate numbers (candidates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target.

Each number in candidates 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. Example 1:

Input: candidates = [10,1,2,7,6,1,5], target = 8, A solution set is: [ [1, 7], [1, 2, 5], [2, 6], [1, 1, 6] ] Example 2:

Input: candidates = [2,5,2,1,2], target = 5, A solution set is: [ [1,2,2], [5] ]

Approach 1: Depth First Search (My Solution)

Idea

Same idea with the last problem the only difference that in the recursion call:, change the index to i+1 to jump to the next item to avoid repeat.

Solution

class Solution1:
    def combinationSum2(self, candidates, target):
        """ 
        :type candidates: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        candidates.sort()
        res = []
        self.dfs(candidates, target, 0, [], res)
        return set([tuple(i) for i in res])

    def dfs(self, candidates, target, index, path, res):
        if target < 0:
            return
        if target == 0:
            res.append(path)
            return
        for i in range(index, len(candidates)):
            self.dfs(candidates, target - candidates[i], i+1, path + [candidates[i]], res)

Complexity

  • Time: $O()$
  • Space: $O()$

Approach 2: Improved DFS (beat 99.56% Python) ***

Idea

Solution

class Solution2:
    def combinationSum2(self, candidates, target):
        # Sorting is really helpful, se we can avoid over counting easily
        candidates.sort()                      
        result = []
        self.combine_sum_2(candidates, 0, [], result, target)
        return result

    def combine_sum_2(self, nums, start, path, result, target):
        # Base case: if the sum of the path satisfies the target, we will consider 
        # it as a solution, and stop there
        if not target:
            result.append(path)
            return

        for i in range(start, len(nums)):
            # Very important here! We don't use `i > 0` because we always want 
            # to count the first element in this recursive step even if it is the same 
            # as one before. To avoid overcounting, we just ignore the duplicates
            # after the first element.
            if i > start and nums[i] == nums[i - 1]:
                continue

            # If the current element is bigger than the assigned target, there is 
            # no need to keep searching, since all the numbers are positive
            if nums[i] > target:
                break

            # We change the start to `i + 1` because one element only could
            # be used once
            self.combine_sum_2(nums, i + 1, path + [nums[i]], 
                               result, target - nums[i])

Complexity

  • Time: $O()$
  • Space: $O()$


  • KF

Comments