algorithm - 如何编写用于生成集合的所有子集的迭代算法？

Question

我编写了递归回溯算法来查找给定集合的所有子集。

void backtracke(int* a, int k, int n)
{
    if (k == n)
    {
        for(int i = 1; i <=k; ++i)
        {
            if (a[i] == true)
            {
                std::cout << i << " ";
            }
        }
        std::cout << std::endl;
        return;
    }
    bool c[2];
    c[0] = false;
    c[1] = true;
    ++k;
    for(int i = 0; i < 2; ++i)
    {       
        a[k] = c[i];
        backtracke(a, k, n);
        a[k] = INT_MAX;
    }
}

现在我们必须以迭代的形式编写相同的算法，该怎么做？

Answer 1

您可以使用二进制计数器方法。任何长度为 n 的唯一二进制字符串表示一组 n 个元素的唯一子集。如果你从 0 开始到 2^n-1 结束，你覆盖了所有可能的子集。计数器可以很容易地以迭代方式实现。

Java 代码:

  public static void printAllSubsets(int[] arr) {
    byte[] counter = new byte[arr.length];

    while (true) {
      // Print combination
      for (int i = 0; i < counter.length; i++) {
        if (counter[i] != 0)
          System.out.print(arr[i] + " ");
      }
      System.out.println();

      // Increment counter
      int i = 0;
      while (i < counter.length && counter[i] == 1)
        counter[i++] = 0;
      if (i == counter.length)
        break;
      counter[i] = 1;
    }
  }

请注意，在 Java 中可以使用 BitSet，这确实使代码更短，但我使用字节数组来更好地说明该过程。