子集生成算法：位运算 vs 递归 - 代码效率比较

本文分析了两种生成子集的算法：位运算和递归。

'代码1' 利用位运算的方式遍历所有子集，每个数字都有两种状态：选中和不选中。通过循环和位运算，可以快速得到所有子集。

'代码2' 利用递归的方式遍历所有子集，每次递归时都有两个选择：选中当前数字和不选中当前数字。通过递归调用，可以得到所有子集。

'代码1' 的时间复杂度为 O(2^n)，而 '代码2' 的时间复杂度也为 O(2^n)。因此，两段代码的时间复杂度是相同的。

'代码1' 的执行速度更快的原因可能是因为位运算比递归调用更高效。在 '代码1' 中，只需要进行一次循环和一次位运算就可以得到一个子集，而在 '代码2' 中，需要进行多次递归调用才能得到一个子集。因此，'代码1' 的执行速度更快。

以下是代码示例：

class Solution {
    var t = [Int]()
    var ans = [[Int]]()
    func subsets(_ nums: [Int]) -> [[Int]] {
        let n = nums.count
        for mask in 0..<1 << n {
            t.removeAll()
            for i in 0..<n {
                if mask & 1 << i != 0 {
                    t.append(nums[i])
                }
            }
            ans.append(t)
        }
        return ans
    }
}//代码1
class Solution {
    var res = [[Int]]()
    func subsets(_ nums: [Int]) -> [[Int]] {
        var cur = [Int]()
        dfs(nums, &cur, 0)
        return res
    }
    func dfs(_ nums: [Int], _ cur: inout [Int], _ i: Int) {
        res.append(cur)
        if i >= nums.count {
            return
        }
        for j in i..<nums.count {
            let val = nums[j]
            cur.append(val)
            dfs(nums, &cur, j + 1)
            cur.removeLast()
        }
    }
}//代码2

总而言之，在子集生成问题中，位运算算法的效率更高，因为其执行过程更为简洁，避免了递归调用的开销。