40. Combination Sum II

Description:

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

Each number in candidates may only be used once in the combination.

Note: The solution set must not contain duplicate combinations.

 

'''
[1] brute force)

Idea:
find all combinations
check sum of combination in combinations whether it is equal to target or not

- T/C: same as solution[2]
- S/C: same as solution[2]

'''

'''
[2] brute force - using itertools - Time Limit Exceeded)

code:
from itertools import combinations

ans=[]
for i in range(1,len(candidates)+1):
    for comb in combinations(candidates,i):
        if sum(comb)==target:
            ans.append(sorted(list(comb)))
        
ans=list(map(tuple,ans))
return set(ans)

- T/C: O(2^n+log(1^1 * 2^2 * ... * n^n)) # for all comb => nC1+nC2+nC3+...+nCn = 2^n -1, n==len(candidates)
                                         # for sorting => O(1log1)+O(2log2)+...+O(nlogn)=O(log(1^1 * 2^2 * 3^3 *...* n^n))
                                         # for set() => O(len(ans)), I can guess it is smaller than other operations
- S/C: O(1)
'''

'''
[3] back tracking)

Idea:
if sum(list at some moment)>target, we can back
and by sorting input array, it is easier to avoiding duplicates

def bf(ans,cur_list,low,target):
    if sum(cur_list)==target:
        ans.append(cur_list)
        return
    elif sum(cur_list)>target or low>=len(candidates):
        return
    for i in range(low,len(candidates)):
        if i>low and candidates[i]==candidates[i-1]:    # avoiding duplicates
            continue
        bf(ans,cur_list+[candidates[i]],i+1,target)
        
if sum(candidates)<target:
    return []
        
ans=[]
candidates.sort()
bf(ans,[],0,target)
return ans

- T/C: O(2^n)   # when considering all possibility (especially, when there are no back tracking case)
- S/C: O(n)     # for call stack, when nCn case
'''

class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        def bf(ans,cur_list,low,target):
            if sum(cur_list)==target:
                ans.append(cur_list)
                return
            elif sum(cur_list)>target or low>=len(candidates):
                return
            for i in range(low,len(candidates)):
                if i>low and candidates[i]==candidates[i-1]:    # avoiding duplicates
                    continue
                bf(ans,cur_list+[candidates[i]],i+1,target)
        
        if sum(candidates)<target:
            return []
        
        ans=[]
        candidates.sort()
        bf(ans,[],0,target)
        return ans