Array: Combination Sum

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

LeetCode - The World's Leading Online Programming Learning Platform

 

너무 쉬운 간단한 backtracking 문제

 

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

        def dfs(comb, ind, remaining):
            if remaining == 0:
                answer.append(comb[:])
                return

            for i in range(ind, len(candidates)):
                if remaining >= candidates[i]:
                    dfs(comb + [candidates[i]], i, remaining - candidates[i])
        
        dfs([], 0, target)

        return answer