子集为什么是2的n次方

用程序猿脑子来思考下：

看见子集个数公式： 2 n 2^n 2n，想到是多个2 相乘： 2 ∗ 2... ∗ 2 2*2...*2 2∗2...∗2 意味着原集合每多一个元素子集的数量就翻倍。

子集就是从原集合取一些元素和不取一些元素然后构成一个新的集合。 取和不取的组合，像不像0、1开关，二进制?

举个例子:

所以子集个数问题，转化为 n个比特位能表示多少不同情况？ 原集合每多一个元素，子集数量就翻倍，因为它多一个比特位 : ）

显然，每个比特位只有0和1两种取值，n个比特位就能表示 2 n 2^n 2n种情况。 也就是n个元素的集合，有 2 n 2^n 2n个子集。 。 。 。 。 还有组合公式 ∑ i = 0 n C n i = 2 n \sum^n_{i = 0} C_{n}^{i} = 2^n ∑i=0n​Cni​=2n 一样可以用n比特位可以表示多少中不同情况的思维来理解。