LeetCode - 39. Combination Sum [Python]

https://leetcode.com/problems/combination-sum/

Combination Sum - LeetCode

---

풀이 과정

배열로 주어진 수들의 중복조합의 합이 target이 되는 경우를 구하는 문제이다.

 

https://greentea31.tistory.com/196?category=947572 

LeetCode - 77. Combinations [Python]

위 문제를 해결했던 것 처럼 어떤 수를 고르고, 안고르고의 경우를 재귀함수로 계산하게끔 하였다. 단 이번 문제는 중복조합이므로, 어떤 수를 골랐어도 다음에도 또 고를 수 있으므로, 어떤 수를 골라서 sum_value가 증가하는 경우, 고를지 말지 판별해야 하는 index가 증가하게끔 하지 않았다.

 

어떤 수를 고르지 않는 경우에는 index+1을 시켜줘야 한다.

 

i 안 고름 -> i 안 고름 -> i 안 고름 -> 무한반복 -> i 고름

i 고름

 

는 같은 경우인데 연산 과정만 늘어나고 재귀를 탈출하지도 못하기 때문이다.

---

소스 코드

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        answer = []
        output = []
        
        def combination(index, sum_value):
            if sum_value >= target:
                if sum_value == target:
                    answer.append(output[:])
                return
            if index >= len(candidates):
                return
                
            output.append(candidates[index])
            combination(index, sum_value + candidates[index])
            output.pop()
            combination(index+1, sum_value)
        
        combination(0, 0)
        return answer