Imprimir {1,2,3Todos los subconjuntos de ..., sin necesidad de usar un array o bucle en el programa C

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

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

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

Ejemplo

Entrada:　{　3
Salida:　{　1　2　3　}{　1　2　}{　1　3　}{　1　}{　2　3　}{　2　}{　3　}{　}
解释：集合将是{1　2　3从其中我们将找到子集
Entrada:　{　4
Salida:　{　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　}{　}

Método que usaremos para resolver el problema dado-

• Desde num = 2 ^ n -1Empieza en 0.

• Considere la representación binaria de num con n dígitos.

• Desde el representante1Comenzando por el bit más significativo de num, el segundo bit representa2Hasta que represente el bit n del número n.

• Imprimir el número correspondiente al bit (si está configurado).

• Ejecutar los pasos anteriores para todos los valores de num hasta que sea igual a 0.

Vamos a usar un ejemplo simple para entender mejor cómo funciona el método-

Supongamos que la entrada n = 3Entonces el problema se convierte en num = 2 ^ 3-1 = 7Inicio　

• 7⇒ Forma binaria

• Subconjunto correspondiente ⇒

Restar de num1；num = 6

• 6Forma binaria ⇒

• Subconjunto correspondiente ⇒

Restar de num1；num = 5

• 5Forma binaria ⇒

• Subconjunto correspondiente ⇒

Restar de num1；num = 4

• Forma binaria4⇒

• Subconjunto correspondiente ⇒

Del mismo modo, iteraremos hasta que num = 0 e imprimiremos todos los subconjuntos.

Algoritmo

Inicio
　　　Paso　1　→ En la función int subset(int bitn, int num, int num_of_bits)
　　　Si bitn >= 0
　　　　　　Si (num & (1　<< bitn)) != 0
　　　　　　　　　Imprimir num_of_bits　-　bitn
　　　　　　　　　subset(bitn　-　1,　num,　num_of_bits);
　　　　　　De lo contrario
　　　　　　　　　Retornar 0
　　　　　　Retornar　1
　　　Paso　2　→ En la función int printSubSets(int num_of_bits, int num)
　　　　　　Si (num >= 0)
　　　　　　　　　Imprimir "{ "
　　　　　　　　　Llame a la función subset(num_of_bits　-　1, num, num_of_bits)
　　　　　　　　　Imprimir ","
　　　　　　　　　Llame a la función printSubSets(num_of_bits, num　-　1)
　　　　　　De lo contrario
　　　　　　　　　Retornar 0
　　　　　　Retornar　1
　　　Paso　3　→ En la función int main()
　　　　　　Declarar e inicializar int n =　4
　　　　　　Llame a la función printSubSets(n, (int) (pow(2,　n))　-1)
Detener

Ejemplo

#include <stdio.h>
#include <math.h>
//　Esta función imprime recursivamente la
//　subconjunto correspondiente al binario
//　representación de num.
int subset(int bitn, int num, int num_of_bits) {
　　　if　(bitn　>=　0)　{
　　　　　　//　Imprimir el número en el subconjunto dado solo
　　　　　　//　si el bit correspondiente a él
　　　　　　//　está configurado en num.
　　　　　　if　((num　&　(1　<<　bitn))　!=　0)　{
　　　　　　　　　printf("%d　",　num_of_bits　-　bitn);
　　　　　　}
　　　　　　//　Revisar el siguiente bit
　　　　　　subset(bitn　-　1,　num,　num_of_bits);
　　　}
　　　else
　　　　　　return　0;
　　　　　　return　1;
}
//función para imprimir los subconjuntos
int　printSubSets(int　num_of_bits,　int　num)　{
　　　if　(num　>=　0)　{
　　　　　　printf("{　");
　　　　　　//　Imprimir los subconjuntos correspondientes a
　　　　　　//　la representación binaria de num.
　　　　　　subset(num_of_bits　-　1,　num,　num_of_bits);
　　　　　　printf("}");
　　　　　　//　llamando recursivamente la función para
　　　　　　//　imprimir el siguiente subconjunto.
　　　　　　printSubSets(num_of_bits,　num　-　1);
　　　}
　　　else
　　　　　　return　0;
　　　　　　return　1;
}
//programa principal
int　main()　{
　　　int　n　=　4;
　　　printSubSets(n,　(int)　(pow(2,　n))　-1);
}

Resultado de salida

{　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　}{　}