ac solution code


  • 0
    // Solution1. DFS Recursive - time = O(n!); space = O(n) - path
     func subsets(_ nums: [Int]) -> [[Int]] {
            var res = [[Int]]()
            var path = [Int]()
            dfs(nums, 0, &path, &res)
            return res
        }
        /// All subsets starting with nums[start]
        private func dfs(_ nums: [Int], _ start: Int, _ path: inout[Int], _ res: inout [[Int]]) {
            // (termination case)
            res.append(Array(path))// Add all possible subsets to the result
            // As path only contains nums[0..start-1] elements, so impossible to contain nums[start..n-1], no need to check
            for i in start..<nums.count {
                path.append(nums[i])
                dfs(nums, i + 1, &path, &res)// Next start should be i + 1
                path.removeLast()// Backtracking
            }
        }
    
        // Solution2. Non-Recursive - time = O(n!); space = O(n)
        func subsets2(_ nums: [Int]) -> [[Int]] {
            var res = [[Int]]()
            res.append([Int]())
            let nums = nums.sorted(by: <)
            for x in nums {
                var curSubs = [[Int]]()// Add all subsets ending with x
                for sub in res {
                    var curSub = [Int](sub)
                    curSub.append(x)
                    curSubs.append(curSub)
                }
                res.append(contentsOf: curSubs)
            }
            return res
        }
    
    // Solution3. Bit manipulation
         func subsets(_ n: [Int]) -> [[Int]] {
            var nums = n
            nums.sort {$0 < $1}
            let elemNum = nums.count
            let subsetNum = Int(pow(2.0, Double(elemNum)))
            var subsets: [[Int]] = [[Int]](repeating: [], count: subsetNum)
            for i in 0..<elemNum {
                for j in 0..<subsetNum {
                    if ((j >> i) & 1) != 0 {
                        subsets[j].append(nums[i])
                    }
                }
            }
            return subsets
        }
    

Log in to reply
 

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