# ac solution code

• ``````// 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
}
``````

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