leetCodeArrayHard.swift

// https://leetcode.com/problems/subsets/
// Approach 1: Cascading
// Time: O(n*2^n), Space: O(n*2^n)
func subsets(_ nums: [Int]) -> [[Int]] {
    var result = [[Int]]()
    result.append([])
    for num in nums {
        for currSet in result {
            result.append(currSet + [num])
        }
    }

    return result
}

// Approach 2: Backtracking
// Time: O(n*2^n), Space: O(n*2^n)
func subsets(_ nums: [Int]) -> [[Int]] {
    var result = [[Int]]()
    var currSet = [Int]()
    backtrack(0, &currSet, &result, nums)
    return result
}

func backtrack(_ start: Int, _ currSet: inout [Int], _ result: inout [[Int]], _ nums: [Int]) {
    result.append(currSet)
    for i in start..<nums.count {
        currSet.append(nums[i])
        backtrack(i + 1, &currSet, &result, nums)
        currSet.removeLast()
    }
}


// Approach 3: Lexicographic (Binary Sorted)
// Time: O(n*2^n), Space: O(n*2^n)
func subsets(_ nums: [Int]) -> [[Int]] {
    var result = [[Int]]()
    let lower = 1 << nums.count
    let upper = 1 << (nums.count + 1)

    for i in lower..<upper {
        let binaryString = String(i, radix: 2).dropFirst()

        var subset = [Int]()
        for (index, char) in binaryString.enumerated() {
            if char == "1" { subset.append(nums[index]) }
        }
        result.append(subset)
    }

    return result
}


// Approach 4: Bit Manipulation
// Time: O(n*2^n), Space: O(n*2^n)
func subsets(_ nums: [Int]) -> [[Int]] {
    let count = nums.count
    let subsetCount = 1 << count // = 2^count
    var result = Array(repeating:[Int](), count: subsetCount)
    for i in 0..<subsetCount {
        for j in 0..<count {
            if i >> j & 1 == 1 { 
                result[i].append(nums[j])
            }
        }
    }

    return result
}