[LeetCode] 39번 - Combination Sum [Swift]

문제 링크

Combination Sum - LeetCode

문제 

Given an array of distinct integers candidates and a target integer target, return a list of all unique combinations of candidateswhere 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]]

 

Constraints:

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

문제 풀이

이 문제는 주어진 정수 배열에 존재하는 정수들의 합으로 target을 만들 수 있는 조합을 모두 구하는 문제인데요, 중요한 것은 중복을 허용한다는 것 입니다.

 

예로 나와있는 [2,3,5]로 8을 만드는 조합을 모두 구할 때 [2,2,2,2]도 될 수 있다는 말이죠.

즉 주어진 숫자로 만들 수 있는 모든 경우의 수를 구하는데 같은 수를 여러번 넣도록 처리해주면 됩니다.

 

그리고 아무런 조건이 없이 만들게 되면 당연하게도 무한히 동작하기 때문에 target 보다 현재 합이 작을때만 다음 조합을 만들어주도록 처리해주시면 됩니다!

 

백트래킹의 가장 기본이 되는 문제인것 같아요.

소스 코드

class Solution {
    func combinationSum(_ candidates: [Int], _ target: Int) -> [[Int]] {
        
        var result: [[Int]] = []
        
        func combination(_ nowCombination: [Int], _ nowSum: Int, _ index: Int) {
       	    // 만약 현재 합이 target 이라면 현재 조합을 결과에 추가
            if nowSum == target {
                result.append(nowCombination)
                return
            }
            
            if index >= candidates.count {
                return
            }
            
            // 중복을 허용하도록 백트래킹 진행
            for i in index..<candidates.count {
                if nowSum + candidates[i] <= target {
                    combination(nowCombination + [candidates[i]], nowSum + candidates[i], i)
                }
            }
        }
        
        // 백 트래킹 실행
        combination([], 0, 0)
        
        return result
    }
}