algorithm - 2^n 复杂度算法

Question

我需要实现和测试复杂度为 2^n 的算法。我一直试图找到一个。如果有任何方法我可以通过实现来实现这一点——精确复杂度为 2^n 将是最佳的。如果有人知道某个位置，我可以找到一个示例，或者可以帮助我实现一个，那就太棒了:-)。基本操作可以是任何东西，但是像 i++ 这样的单个语句；最好。

Answer 1

生成具有 n 个元素的集合的所有子集。

已添加。生成 S = {a0, a1, ..., an-1} 的所有子集的最简单方法可能是在秩和子集的二进制表示之间进行转换。

取 S = {a0, a1, a2}。

rank binary subset
0    000    {} 
1    001    {a0}
2    010    {a1}
3    011    {a0, a1}
4    100    {a2}
5    101    {a0, a2}
6    110    {a1, a2}
7    111    {a0, a1, a2}

因此，二进制中的 1 表示对应的元素在子集中。 0 表示该元素不在子集中。

但是你还应该查找格雷码。