[LeetCode] 040. Combination Sum II
-
date_range April 04, 2019 - Thursday info
- Problem (Medium)
- Approach 1: Depth First Search (My Solution)
- Approach 2: Improved DFS (beat 99.56% Python) ***
Problem (Medium)
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