LeetCode – 40. Combination Sum II

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

參考解法: https://leetcode.com/problems/combination-sum-ii/discuss/16886/Swift-solution-Backtracking

func combinationSum2(_ candidates: [Int], _ target: Int) -> [[Int]] {
    let arr = candidates.sorted()
    var result: [[Int]] = []
    var cur: [Int] = []
    helper(arr, target, 0, &cur, &result)
    return result
}

func helper(_ candidates: [Int], _ target: Int, _ startIndex: Int, _ cur: inout [Int], _ result: inout [[Int]]) {
    if target < 0 {
        return
    } else if target == 0 {
        result.append(cur)
    } else {
        for i in startIndex ..< candidates.count {
            if i > startIndex && candidates[i] == candidates[i-1] {
                continue
            }
            cur.append(candidates[i])
            helper(candidates, target - candidates[i], i + 1, &cur, &result)
            cur.removeLast()
        }
    }
}