[파이썬 알고리즘] 12장 - 조합의 합 (leetcode 39)

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

Combination Sum - LeetCode

 

<문제>

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.

It is guaranteed that the number of unique combinations that sum up to target is less than 150 combinations for the given input.

 

 

<예시>

Input: candidates = [2,3,6,7], target = 7
Output: [[2,2,3],[7]]
Explanation:
2 and 3 are candidates, and 2 + 2 + 3 = 7. Note that 2 can be used multiple times.
7 is a candidate, and 7 = 7.
These are the only two combinations.


Input: candidates = [2,3,5], target = 8
Output: [[2,2,2,2],[2,3,3],[3,5]]


Input: candidates = [2], target = 1
Output: []


Input: candidates = [1], target = 1
Output: [[1]]

 

 

---

# my solution
# faster than 13% (156ms)
# less than 32% (14.4MB)
class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        def dfs(partial_list, remainder_list):
            if sum(partial_list) == target:
                ans.append(partial_list)
                return
            elif sum(partial_list) > target:
                return
            else:
                for i, value in enumerate(remainder_list):
                    dfs(partial_list+[value], remainder_list[i:])

        ans = []
        candidates.sort()
        dfs([], candidates)
        return ans

 

 

 

 

The same number may be chosen from candidates an unlimited number of times. 

라고 했기 때문에 특정 숫자를 추가한 상황에서 다음에 추가할 숫자를 고려할 때 이전에 추가한 숫자까지 "포함하여" 고려한다.

 

3를 추가한 상황에서 다음에 2를 추가하는 것을 고려하지 않는 이유는 조합에서 "순서는 상관없기" 때문이다.

2를 추가하고 3을 추가하나, 3을 추가하고 2를 추가하나 동일하기 때문에

특정 숫자를 추가한 상황에서 그 다음 후보는 이전에 추가한 값 이상의 숫자가 된다.

 

 

이 문제는 이전 조합, 순열 문제보다 종료조건을 더 꼼꼼히 설정해주어야 했다.

• sum(partial_list)가 target과 일치하면 ans에 추가하고 함수를 리턴한다.
• sum(partial_list)가 target보다 작으면 partial_list에 하나의 숫자를 더 추가해주고 다시 함수를 재귀적으로 호출한다.
• sum(partial_list)가 target보다 크다면 이미 답의 후보에서 탈락이기 때문에 함수를 리턴한다.