Print {1,2,3All subsets of {…n} without using arrays or loops in a C program

Given a positive integer n, we must print a set {1,2,3,4,... n} all subsets.

Just as we would say for any number3 Just like we must print the set {1,2,3All subsets of } that will be {1 2 3,{1 2,{2 3,{1 3, {1,{2,{3}

But we must perform this operation without using any loops or arrays. Therefore, recursion is the only possible method to solve such problems without using any arrays or loops.

Example

Input:　3
Output: {　1　2　3　{}　1　2　{}　1　3　{}　1　{}　2　3　{}　2　{}　3　{}
Explanation: The set will be {1　2　3From 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　{}

The method we will use to solve the given problem-

• From num = 2 ^ n -1Starting from 0.

• Consider the binary representation of num with n bits.

• From the representation1Starting from the most significant bit, the second bit represents2And so on, until the nth bit representing n.

• Print the number corresponding to the bit (if set).

• Perform the above steps for all values of num until it equals 0.

Let us use a simple example to understand the working of the method in detail-

Assuming input n = 3Then the problem becomes num = 2 ^ 3-1 = 7Start　

• 7⇒binary representation

• Corresponding subset⇒

Subtract from num1; num = 6

• 6binary representation⇒

• Corresponding subset⇒

Subtract from num1; num = 5

• 5binary representation⇒

• Corresponding subset⇒

Subtract from num1; num = 4

• binary representation4⇒

• Corresponding subset⇒

Similarly, we will iterate until num = 0 and print all subsets.

Algorithm

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 function printSubSets(n, (int) (pow(2, n))　-1)
Stop

Example

#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("{ ");
　　　　　　//　Print int 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;
}

Output Result

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