看一个数组的子集有多少，其实就是排列组合，
比如：[0,1] 对应的子集有：[] [0] [1] [1,1] 这四种。
一般对应有两种方法： 位运算 和 回溯。
这里先使用位运算来做。
位运算
一个长度为n的数组，对其做排列组合，可以理解为：这n个数字中，有哪些是存在的，哪些是不存在的。
例如，数组为[1,2,3]，可以组合为：[1,2]，则说明1和2是存在的，3是不存在的，
我们可以这么规定一下： 用1标记为存在，0标记为不存在，
那么[1,2]这个组合就可以用 110来标记，[1,3]的组合就可以用101来标记，[]的组合就可以用000来标记。
（注：这里为方便理解，将数组直观的位置与标记一一对应，而不考虑数组下标，
实际代码中，是用下标来做对应的）
这样的话：
数组的排列组合问题，就转换为每个数字的存在或者不存在的问题。
这里有三个数字，每个数字都会有存在和不存在的两种情况，总共就会有8种排列，分别是：
000，001， 010， 011， 100， 101， 110， 111
对应的数组分别是：
[]，[3]，[2]， [2,3]， [1]， [1,3]， [1,2]， [1,2,3]
重点来了：如果把上面的01标记看成二进制数字的，那对应的十进制数字就是0,1,2,3,4,5,6,7。
这里先统称这些数字为flag（用来标记对应位置的数字是否存在）。
所以，当我已经知道总共的组合有n种的时候，那么就会有 0 到 (n-1) 个 flag 来标记对应位置的数字是否存在。
那么代码中是怎么对应的呢？这次用数组[6,7,8]来举例。
数字6，7，8对应的下标分别是 0，1，2，对应的位置就是 (1 << 下标)，
那么：6对应的是flag中的第1位（1<
ps：因为题目要求输出的形式是： [[],[3],[2],[2,3],[1],[1,3],[1,2],[1,2,3]]，
这个的话，感觉用c不太好实现，所以就偷偷用了python来实现了，但原理还是一样的！
class Solution(object):
def subsets(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
subList = []
length = len(nums)
totalCount = pow(2, length) # 得到子集的总个数
for flag in range(totalCount): # 遍历各个flag标记
sub = []
for xiabiao in range(length): # 遍历数组下标，查看对应位置的数字是否存在
if flag & (1<<xiabiao): sub.append(nums[xiabiao]) # 如果对应的数字存在，就把该数字放入新数组中 sublist.append(sub) return sublis < code></xiabiao):>
递归放在下一篇讲解。
Original: https://www.cnblogs.com/payapa/p/11124106.html
Author: 努力爬呀爬
Title: leetcode的Hot100系列–78. 子集–位运算
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/565243/
转载文章受原作者版权保护。转载请注明原作者出处！