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.

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

예시

Example 1:
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.

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

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

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

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

풀이

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        res = []
        
        def generate(chosen):
            if sum(chosen) > target: return
            if sum(chosen) == target:
                res.append(chosen[:])
                return
            
            start = candidates.index(chosen[-1]) if chosen else 0
            for nxt in range(start, len(candidates)):
                chosen.append(candidates[nxt])
                generate(chosen)
                chosen.pop()
                
        generate([])
        
        return res

한번 combination 문제를 풀었더니, 조합을 사용하는 문제가 굉장히 많다. 이번 문제도 똑같이 주어진 input에서 target과 같은 결과를 만들어내는 조합을 찾는 문제이지만, 원소 간 중복을 허용하는 조합에서 약간의 차이가 있다.

앞서, 기존의 combination 문제에서는 start의 시작을 원래의 시작 index보다 +1을 해줌으로써 중복을 피할 수 있었다. 그러므로 이번에서는 +1을 하지 않음으로써 중복을 허용할 수 있고 target과 일치하는 조합을 구할 수 있다.