LeetCode 39(Combination Sum , Python)

1. 문제 링크

• 39. Combination Sum

Combination Sum - LeetCode

 

2. 문제 설명

• candidates = [2,3,6,7], target = 7이 주어지면 [[2,2,3],[7]]을 반환하는 문제
• 주어진 리스트의 요소를 합하여 target을 만들 수 있는 모든 경우를 리스트로 만들기
• 이때 각 요소를 횟수 제한 없이 여러 번 사용 가능

3. 처음 풀이

• 스스로 풀지 못하고 GPT에게 답을 알려주지 말고 힌트만 달라고 하였는데 답을 알려줌.
• 풀기 어려웠던 이유는, 그동안 재귀함수를 사용할 때 input 인수가 하나이고 output과 그 형식이 같은 경우만 경험해보았는데(예를 들면 피보나치 수열)
• 이번에는 candidates와 target이 인수로 주어지면 output도 그 형식이라고 생각하였음. 하지만 정답은 이중리스트라 이 사이 간극을 좁히지 못하였었음. 
• 결국 GPT를 통해 답을 보고 나서 스스로 다시 따라해보는 것에 그침. 
• 답지를 보게 되어 너무 속상했지만, 더 고민했어도 못 풀었을 것 같음. 
• 풀이 흐름은...
• candidates에서 요소를 골라 담은 현재 리스트를 path라 하고 path의 합을 전체 target에서 뺀 현재 목표값을 trg라 하자
• trg = 0 이 되면 현재 path가 답지가 되어 ans에 추가한다. 
• candidates의 i번째 요소 num을 path에 넣은 후 (candidates[i:], path, trg-num)에 대해 재귀 때린 후 path.pop()을 한다.
• 백트래킹의 전형적인 꼴이다. 
• path에 append 하고 재귀한 다음에 pop하는 구조가 처음에 잘 이해가 안되었었는데 이 부분이 잘 이해가 안된다면 백트래킹이 아니라 재귀함수가 호출되고 종료되는 순서에 대한 구조에 대해 검색해보는게 맞는 것 같다. 재귀함수는 종료는 실행된 역순으로 된다. 
• 아래 이미지가 이해에 도움임 될 것 같아서 https://yuminlee2.medium.com/combinations-and-combination-sum-3ed2accc8d12에서 가져왔다. 

class Solution:

    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        ans = []

        def helper(lst,path,trg):
            if trg == 0 :
                ans.append(path[:])
                return
            for i, num in enumerate(lst):
                if num <= trg:
                    path.append(num)
                    helper(lst[i:],path,trg-num)
                    path.pop()
        
        helper(candidates,[],target)

        return ans

 

4. 다른 풀이

• DP로도 풀 수 있다. 

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        dp = [[] for _ in range(target+1)]

        for c in candidates:
            for i in range(c, target+1):
                if i==c: dp[i].append([c])
                for comb in dp[i-c]:
                    dp[i].append(comb+[c])
                    
        return dp[-1]

5. 배운 점

• 백트래킹 알고리즘의 논리는 이미 들어서 이해하고 있었지만 이를 재귀함수와 함께 코드로 구현하는 것은 어려웠다. 하지만 이 문제를 고민하면서 익숙해질 수 있었음.