实现自己的集合算法

• 给定一个集合，返回这个集合的所有子集

思路 1 - 位

• 思路：这道题本质上就是元素选与不选的问题，于是我们想到用二进制来代表选与不选的情况。1代表这个元素已经选择，0代表这个元素没有选择，假如3个元素A B C，那么101就代表B没有选择，所以101代表的子集为AC

func getSubsetsOfSet<T>(set: Set<T>) -> Array<Set<T>> {
    let count = 1 << set.count
    let elements = Array(set)
    var subSets = Array<Set<T>>()
    for i in 0..<count {
        var subSet = Set<T>()
        for j in 0...elements.count {
            if ((i >> j) & 1) == 1 {
                subSet.insert(elements[j])
            }
        }
        subSets.append(subSet)
    }
    return subSets
}

思路 2 - 递归

• 思路：如果只有一个元素，那么他的子集有 2 个，分别是本身和空集，然后在已经有1个元素的子集的基础上，第二个元素有2种选法，那就是加入到前面的子集里面或者不加入前面的子集里面，也就是选与不选的问题。而前面的子集一共有2个，对每一个子集都有来自于下一个元素的加入和不加入2种选法。那么就可以得出2个元素的子集一共有4个，依此类推，就可以得出 n 的元素所有子集（这里 n 个元素的子集一共有 2n 个，非空子集一共有 2n - 1 个）