40. Combination Sum II, 파이썬

예전에 풀었을 때는 시간초과 때문에 틀렸던 것 같다. 

[1, 1, 1, 1, 1, 1, 1] 등에서 시간초과가 났었다 

 

문제

1. 숫자들이 배열로 주어졌을 때 합이 target인 숫자 조합을 중복 없이 구하는 것. 

 

풀이

1. 어려운 문제는 아니지만 중복을 피하고, 시간을 줄이는 것이 핵심. 

2. target 8, [1, 1, 4, 6, 7] 이라고 했을 때 [1, 1, 6] 은 체크하고 [1, 7], [1, 7] 이 중복이 나오지 않게 해야한다. 

3. 따라서 정렬된 배열에서 path에서 arr[i] 값이 중복되어 다음 dfs로 넘어가지 않도록 체크해준다. 

class Solution(object):
    def combinationSum2(self, candidates, target):
        ret = []
        self.dfs(sorted(candidates), target, [], ret, 0)
        return ret
    
    def dfs(self, arr, target, path, ret, idx) :
        if target == 0 :
            ret.append(path)
            return
        if idx == len(arr) or arr[idx] > target:
            return
        for i in range(idx, len(arr)) :
            if arr[i] <= target and (i == idx or arr[i] != arr[i-1]):
                self.dfs(arr, target - arr[i], path + [arr[i]], ret, i +1)