[Leetcode 39] - Combination Sum w/ Python

 

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.

 

 

배열과 목표(target) 숫자가 주어지면 배열에 있는 수들을 더해 목표에 더해지는 값들을 저장해 리턴하는 문제

배열에 있는 숫자를 반복적으로 사용할 수 있다

※ 예를 들어 타겟이 8이고 배열에 숫자가 2가 들어가 있으면 2+2+2+2 역시 가능한 방법

 

 

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

 

 

 

---

 

 

 

 

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: []

 

 

 

 

 

---

 

 

 

 

역시 백트래킹을 통해 문제를 풀었다

가장 유의해야될 점은 바로 반복되는 숫자를 처리하는 방식에서 런타임이 극심하게 갈린다

 

 

1. candidates (너무 치기 귀찮아서 c로 변경했다)를 먼저 sort한다

2. index 0으로 시작해서 0에 있는 숫자만 사용해서 풀이가 가능한지 먼저 확인후 0을 다시는 사용 안한다

3. 현재 숫자가 타겟보다 낮으면 타겟을 수정 -> stack에 저장 -> 다음 재귀로 이동

4. 현재 숫자가 타겟보다 높으면 바로 return

 

 

class Solution:
    def combinationSum(self, c, target):
        def backtrack(start, cTarget, stack):
            if cTarget == 0:
                result.append(stack)
                return
            for i in range(start, len(c)):
                if c[i] > cTarget:
                    break
                backtrack(i, cTarget - c[i], stack + [c[i]])
        
        result = []
        c.sort()  
        backtrack(0, target, [])
        return result