leetcode 39. Combination Sum 풀이

문제 : 중복되지 않는 int 로 이루어진 list 에서 부분집합의 합이 target과 동일한 부분집합의 list를 return하라 ( 부분집합을 생성할 때 동일한 원소를 사용해도 된다.)

Follow up : -

 

아이디어 : 모든 경우의 수를 탐색하면서 특정 값을 찾아야하므로 dfs를 사용하기로 했다. 재귀 형태를 사용하며 탈출조건은 sum과 target이 같아지면 path를 return 하기로 했다.

 

코드 :

 

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        global ans
        ans = []
        def dfs(path: List[int], index: int, s: int) -> List[List[int]]:
            global ans
            if s == target:
                #print(path)
                ans.append(path)
                return path
            for i in range(index, n):
                t = candidates[i]
                if (t + s) <= target:
                    if path:
                        p = path[:]
                    else:
                        p = []
                    p.append(t)
                    #print(path, p, i, s, t)
                    dfs(p, i, s + t)
        n = len(candidates)
        dfs([], 0, 0)
        return ans

 

학습 포인트 : dfs(p, i, s+t) 대신에 dfs(p.append(t), i , s+t) 를 했을 때 return 이 None이 나왔었다. 이는 append 자체의 return값은 append된 리스트 값이 아닌 None 이기 때문이다. 이 부분을 유념해서 코드를 작성해야겠다.

 

출처 : leetcode.com/problems/combination-sum/