LeetCode 216. Combination Sum III

题目

Find all possible combinations of k numbers that add up to a number n, given that only numbers from 1 to 9 can be used and each combination should be a unique set of numbers.

Note:

All numbers will be positive integers.  
The solution set must not contain duplicate combinations.  
Example 1:

Input: k = 3, n = 7  
Output: [[1,2,4]]  
Example 2:

Input: k = 3, n = 9  
Output: [[1,2,6], [1,3,5], [2,3,4]]  

思路

跟Combination sum I, II 的思路差不多,只是换了些新的限制条件, 个数为k个,不重复, nums 为1-9

Swift 题解

func combinationSum3(_ k: Int, _ n: Int) -> [[Int]] {  
        let nums: [Int] = Array(1...9)

        var result = [[Int]]()
        var current = [Int]()

        dfs(nums: nums, size: k, target: n, result: &result, current: &current, level: 0)

        return result
    }

    func dfs(nums: [Int], size: Int, target: Int, result: inout [[Int]], current: inout [Int], level: Int) {
        if target < 0 {
            return
        }

        if current.count == size {
            if target == 0 {
                result.append(current)
            }

            return
        }

        for i in level..<nums.count {
            current.append(nums[i])
            dfs(nums: nums, size: size, target: target - nums[i], result: &result, current: &current, level: i + 1)
            current.removeLast()
        }

    }

chenbo

编程爱好者

Singapore