39. Combination Sum

Category	ps/bfs & dfs
Tag	bfs & dfs
Tags	combination
난이도	★★
발행 여부
사이트	Leet code
실수 유형
이해	완벽히 이해
최종 편집 일시	@2021년 12월 10일 오후 10:29
푼 날짜	@2021년 12월 10일 오후 10:15

문제 해설 및 주의사항

원문

번역 및 주의사항

풀이

내 풀이 코드

풀이 코드

퇴고

문제 해설 및 주의사항

원문

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

번역 및 주의사항

• candidates : 조합의 후보

• target : 조합의 합이 target 이어야 한다.

• 중복 선택이 가능하다.

• target 이 조합의 합인 조합을 모두 retrun 하라.

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

Constraints:

• 1 <= candidates.length <= 30

• 1 <= candidates[i] <= 200

• All elements of candidates are distinct.

• 1 <= target <= 500

---

풀이

내 풀이 코드

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        
        ans = []
        def dfs(index: int, path: List): 
            # 기저사례 : 현재 path 의 합이 target 과 같다면
            current_sum = sum(path)
            
            if current_sum == target :
                ans.append(path[:])
                return
            elif current_sum > target:
                return
            
            for i in range(index, len(candidates)):
                path.append(candidates[i])
                dfs(i, path)
                path.pop()
        
        dfs(0, [])
        return ans

풀이 코드

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        
        ans = []
        def dfs(index: int, path: List, current_sum): 
            # 기저사례 : target 부터 시작한 current_sum 이 점점 빼지면서 0에 다다른다면
            if current_sum == 0 :
                ans.append(path[:])
                return
            elif current_sum < 0:
                return
            
            for i in range(index, len(candidates)):
                path.append(candidates[i])
                dfs(i, path, current_sum - candidates[i])
                path.pop()
        
        dfs(0, [], target)
        return ans

---

퇴고