ac solution code


  • 0
    /*
         Solution1. time = C(n, k); space = O(k) - solution
         The basic idea is to use backtracking to combin numbers from start..n, then start+1..n recursively
         */
         func combine(_ n: Int, _ k: Int) -> [[Int]] {
            var res = [[Int]]()
            var path = [Int]()
            DFS(n, k, &res, &path, 1)//<-- start from 1
            return res
        }
        private func DFS(_ n: Int, _ k: Int, _ res: inout [[Int]], _ path: inout [Int], _ start: Int) {// start: speicify the smallest selectable number
            if path.count == k {// Termination case
                res.append(path)
                return
            }
            for i in start ..< n + 1 {//<-- end at n
                path.append(i)// append i to current path
                DFS(n, k, &res, &path, i + 1)// sub recurse  i + 1...n
                path.removeLast()// remove i from current path
            }
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.