打印{1,2,3，…n}的所有子集，而无需在C程序中使用数组或循环

给定正整数n，我们必须在不使用任何数组或循环的情况下打印一组{1,2,3,4，... n}的所有子集。

就像我们给任何数字说3 s一样，我们必须打印集合{1，2，3}中的所有子集，它们将是{1 2 3}，{1 2}，{2 3}，{1 3}， {1}，{2}，{3} {}。

但是我们必须在不使用任何循环或数组的情况下执行此操作。因此，仅递归是解决此类问题的可能方法，而无需使用任何数组或循环。

示例

Input: 3
Output: { 1 2 3 }{ 1 2 }{ 1 3 }{ 1 }{ 2 3 }{ 2 }{ 3 }{ }
Explanation: The set will be {1 2 3} from which we will find the subsets
Input: 4
Output: { 1 2 3 4 }{ 1 2 3 }{ 1 2 4 }{ 1 2 }{ 1 3 4 }{ 1 3 }{ 1 4 }{ 1 }{ 2 3 4 }{ 2 3 }{ 2 4 }{ 2 }{ 3 4 }{ 3 }{ 4 }{ }

我们将用来解决给定问题的方法-

• 从num = 2 ^ n -1到0开始。

• 考虑具有n个位数的num的二进制表示形式。

• 从代表1的最左位开始，第二位代表2，依此类推，直到代表n的第n位。

• 打印与该位对应的数字（如果已设置）。

• 对num的所有值执行上述步骤，直到等于0。

让我们使用一个简单的示例来详细了解 方法的工作方式-

假设输入n = 3，那么问题就从num = 2 ^ 3-1 = 7开始 

• 7⇒的二进制表示形式

• 对应子集⇒

从num减去1；num = 6

• 6的二进制表示⇒

• 对应子集⇒

从num减去1；num = 5

• 5的二进制表示形式⇒

• 对应子集⇒

从num减去1；num = 4

• 二进制表示形式4⇒

• 对应子集⇒

同样，我们将迭代直到num = 0并打印所有子集。

算法

Start
   Step 1 → In function int subset(int bitn, int num, int num_of_bits)
   If bitn >= 0
      If (num & (1 << bitn)) != 0
         Print num_of_bits - bitn
         subset(bitn - 1, num, num_of_bits);
      Else
         Return 0
      Return 1
   Step 2 → In function int printSubSets(int num_of_bits, int num)
      If (num >= 0)
         Print "{ "
         Call function subset(num_of_bits - 1, num, num_of_bits)
         Print "}"
         Call function printSubSets(num_of_bits, num - 1)
      Else
         Return 0
      Return 1
   Step 3 → In function int main()
      Declare and initialize int n = 4
      Call fucntionprintSubSets(n, (int) (pow(2, n)) -1)
Stop

示例

#include <stdio.h>
#include <math.h>
// This function recursively prints the
// subset corresponding to the binary
// representation of num.
int subset(int bitn, int num, int num_of_bits) {
   if (bitn >= 0) {
      // Print number in given subset only
      // if the bit corresponding to it
      // is set in num.
      if ((num & (1 << bitn)) != 0) {
         printf("%d ", num_of_bits - bitn);
      }
      // Check the next bit
      subset(bitn - 1, num, num_of_bits);
   }
   else
      return 0;
      return 1;
}
//function to print the subsets
int printSubSets(int num_of_bits, int num) {
   if (num >= 0) {
      printf("{ ");
      // Printint the subsets corresponding to
      // the binary representation of num.
      subset(num_of_bits - 1, num, num_of_bits);
      printf("}");
      // recursively calling the function to
      // print the next subset.
      printSubSets(num_of_bits, num - 1);
   }
   else
      return 0;
      return 1;
}
//main program
int main() {
   int n = 4;
   printSubSets(n, (int) (pow(2, n)) -1);
}

输出结果

{ 1 2 3 4 }{ 1 2 3 }{ 1 2 4 }{ 1 2 }{ 1 3 4 }{ 1 3 }{ 1 4 }{ 1 }{ 2 3 4 }{ 2 3 }{ 2 4 }{ 2 }{ 3 4 }{ 3 }{ 4 }{ }