[LeetCode 해석 및 풀이] 39. Combination Sum(조합 합)

LeetCode 문제 해석 및 풀이 방법

문제 39. Combination Sum(조합합)

난이도 : 중간🟡 바로가기

 

문제 설명

영문

Given an array of distinct integers candidates and a target integer target, return a list of all unique combinations of candidates where the chosen numbers sum to target. You may return the combinations in any order.

 

The same number may be chosen from candidates an unlimited number of times. Two combinations are unique if the frequency of at least one of the chosen numbers is different.

 

The test cases are generated such that the number of unique combinations that sum up to target is less than 150 combinations for the given input.

 

한글

서로 다른 정수 candidates 배열과 대상 정수 target이 주어지면 선택한 수 의 합이 target 에 해당하는 모든 고유한 candidates 원소 수 조합  목록을 반환합니다. 답은 아무 순서로 반환해도 상관 없습니다.

 

 candidates 중에서 같은 번호는 무제한으로 선택할 수 있습니다. 선택한 수 중 하나 이상의 빈도가 다른 경우 두 가지 조합은 고유합니다.

 

테스트 케이스는 target에 이 만들어지는 고유 조합 수가 주어진 입력에 대해 150 미만이 되도록 생성됩니다.

 

제한조건

• 1 <= candidates.length <= 30
• 2 <= candidates[i] <= 40
• All elements of candidates are distinct.
• 1 <= target <= 40

 

입출력 예

입력	출력
candidates = [2,3,6,7], target = 7	[[2,2,3],[7]]
candidates = [2,3,5], target = 8	[[2,2,2,2],[2,3,3],[3,5]]
candidates = [2], target = 1	[]

 

해답 및 해설

파이썬 (Python)

백트래킹 알고리즘을 이용한 풀이

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

        def helper(target, depth, num_temp):
            for i in range(depth, len(candidates)):
                check_num = candidates[i]
                if target > check_num:
                    helper(target - check_num, i, num_temp + [check_num])
                elif target == check_num:
                    answer.append(num_temp + [check_num])
                    return
                else:
                    return
        
        helper(target, 0, [])

        return answer

neetcode 로드맵에 나온대로 백트래킹을 이용한 풀이이다. 재귀를 이용, 숫자 하나를 골랐을 때 그 다음 숫자를 고르는 가짓수를 전부 생각해주어 풀면 된다.

 

동적 계획법을 이용한 풀이

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

        for c in candidates:
            if c > target:
                continue

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

동적 계획법으로 합이 특정 수가 되는 candidates 원소 조합을 저장해두는 방식. 이런 숫자 더하기 문제에서는 으레 이렇게 풀곤한다.