題目連結: https://leetcode.com/problems/combination-sum/

參考解法: https://www.youtube.com/watch?v=zIY2BWdsbFs

func combinationSum(_ candidates: [Int], _ target: Int) -> [[Int]] {
    var ans: [[Int]] = []
    var cur: [Int] = []
    let candidateArr = candidates.sorted()
    dfs(candidateArr, target, 0, &cur, &ans)
    return ans
}

func dfs(_ candidates: [Int], _ target: Int, _ startIndex: Int, _ cur: inout [Int], _ ans: inout [[Int]]) {
    if target == 0 {
        ans.append(cur)
        return
    }
    
    for i in startIndex ..< candidates.count {
        if candidates[i] > target {
            break
        }
        cur.append(candidates[i])
        dfs(candidates, target - candidates[i], i, &cur, &ans)
        cur.removeLast()
    }
}