algorithm - 不使用数组递归创建所有子集

Question

我们得到非负整数n来自用户，我们必须打印集合 ({1,2,3,...,n}) 的所有子集. ( n<=20 )

例如 n=3我们必须打印:

{1 , 2 , 3}
{1 , 2}
{1 , 3}
{1}
{2 , 3}
{2}
{3}
{}

, s 是可选的，序列可以不带任何逗号打印。 (如 {1 2 3})我必须补充一点，子集的顺序必须与示例完全相同。意思首先是有 1 的子集，然后是有 2 的子集和...。必须首先打印最长的子集。 (从最大子集(集合本身)到空集的字典顺序)

我在网上看到很多代码都是用数组或者用位数组来表示我们是否使用数字来解决这个问题的。问题是，在这个问题中，我们不允许使用任何类型的数组或其他数据结构，如 vector 等。即使使用像字符串这样的数组行为也是完全禁止的。它必须只能用递归来解决。

我们也不允许使用任何高级功能。例如，如果我们用 C 来写它, 我们可以使用 stdio.h或 C++ , 只有 <iostream>是允许的，没有其他图书馆。

如果没有任何数组，我不知道该怎么做。如何检查它必须打印哪个数字，同时管理 {} .

PS1。问题只是具有这些条件的发电组:

完全禁止使用数组、字符串和偶数循环。只是递归。

用户 Kosyr 提交了一个关于位运算符的非常好的答案。因此，如果您想提交另一个答案，请提交一个甚至不使用位运算符的答案。

PS2.

我在 George 的帮助下编写了这段代码，但它运行不正常。它没有像 1 2 4 这样的东西。它还会重复一些情况。

#include <stdio.h>


void printAllSets (int size)
  {printRows (size, 1);}

void printRows (int size , int start)
{
  if (start<=size)
  {printf( "{ ");
  printRow (start, size);
  printf ("}");
  printf ("\n");}
  if (start <= size)
  {printRows(size -1 , start);
    printRows (size , (start + 1));}
}
printRow (int start, int limit)
{

  if (start <= limit)
  {

    printf ("%d ",start);
    printRow (start +1, limit);
  }
}


int main()
{
    printAllSets(5);
    printf("{ }");
    return 0;
}

PS3.

用户 Kosyr 提交了一个关于位运算符的非常好的答案。因此，如果您想提交另一个答案，请提交一个甚至不使用位运算符的答案。

Answer 1

递归算法非常占用内存。这里的算法为n <= 31

#include <iostream>

void bin(unsigned bit, unsigned k, unsigned max_bits) {
    if (bit == max_bits) {
        std::cout << "{";
        bin(bit - 1, k, max_bits);
    }
    else {
        if ((k & (1u << bit)) != 0) {
            std::cout << (max_bits - bit) << " ";
        }
        if (bit != 0) {
            bin(bit - 1, k, max_bits);
        }
        else {
            std::cout << "}" << std::endl;
        }
    }
}

void print(unsigned k, unsigned n, unsigned max_bits) {
    bin(max_bits, k, max_bits);
    if (k != 0) {
        print(k - 1, n, max_bits);
    }
}

int main()
{
    unsigned n;
    std::cin >> n;
    print((1u << n) - 1u, 1u<<n, n);
    return 0;
}

第一次递归 print枚举 k来自 2^n-1至 0 , 第二次递归 bin枚举 k 的所有位并打印非零位。例如，max_bits = 5和 k = 19是10011b = 16 + 2 + 1 = 2^4 + 2^1 + 2^0 , 位 4,1,0按集互操作 {5-4,5-1,5-0} => {1,4,5}