[LeetCode] Combination Sum

카테고리 (Category)	작성 날짜 (Write Date)	최근 수정 날자 (Recent Write Date)	작성자 (Writer)
Algorithm	2020.04.21. 21:49:52	2020.04.21. 21:49:52	Dev.Yang

 

[문제내용]

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.

 

📄 Combination Sum for Swift Source Code

class Solution {
    
func sumCombination(target: Int, candidate: [Int], temp: inout [Int], result: inout Set<[Int]>) {
    
    let total: Int = temp.reduce(Int.zero, +)
    
    // 찾고자 하는 값이 목표의 값보다 더 큰 경우에는 함수를 종료합니다.
    if target < total { return }
    
    // 찾고자 하는 값이 목표의 값과 동일한 경우에는 현재 값을 저장한 뒤 함수를 종료합니다.
    if target == total {
        result.insert(temp.sorted())
        return
    }
    
    for value in candidate {
        temp.append(value)
        sumCombination(target: target, candidate: candidate, temp: &temp, result: &result)
        temp.removeLast()
    }
}

// MARK: - The same number may be chosen from candidates an unlimited number of times.
func combinationSum(_ candidates: [Int], _ target: Int) -> [[Int]] {
    
    var temp: Array<Int> = []
    var result: Set<[Int]> = []
    
    // MARK: - return a list of all unique combinations of candidates where the chosen numbers sum to target.
    sumCombination(target: target, candidate: candidates, temp: &temp, result: &result)
    
    // MARK: - You may return the combinations in any order.
    return Array(result)
}
}

---

🚀 REFERENCE

Combination Sum - LeetCode

ChangYeop-Yang/Study-Algorithm