[Python] Leetcode - Combination Sum

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

Combination Sum - LeetCode

# 요즘 연습하고 있는 백트래킹 문제이다. candidates의 수들 중 합이 target인 배열을 return하는 문제이다.

 

# 6번째 줄에서 comb를 바로 append하면 안되고, comb.copy()를 append해줘야 answer에 

   값이 제대로 들어간다.

 

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        def BT(prev, target_sum, comb):
            # 종료 조건
            if target_sum == 0:
                answer.append(comb.copy())
            elif target_sum < 0:
                return
            
            for i in range(prev, len(candidates)):
                # candidates의 가능한 원소들 필터링
                num = candidates[i]
                
                # 재귀 호출
                comb.append(num)
                BT(i, target_sum - num, comb)
                comb.pop()
                
        answer = []
        if not candidates:
            return []
        BT(0, target, [])
        return answer