Find all subsets of an array c++

Write a program to find all subsets of an array in c/c++.

Example,

Input
1 2 3 4
Output

4
3
3 4
2
2 4
2 3
2 3 4
1
1 4
1 3
1 3 4
1 2
1 2 4
1 2 3
1 2 3 4

We can implement the program in 2 ways:-

1. Recursively
2. Iteratively (loop)

Find all subsets of an array using Recursion

This approach is very simple. For each element in the input array, we have 2 options. Either include the ith element in the subset or do not include it. We use a temporary array to store the subset. We print the subset array once we traversed all the elements of the array.

Steps

1. Define a recursive function that will accept 5 parameters – the input array, current index of the input array, length of the input array, subset array, the current size of subset array.
2. If the current index of the input array is equal to the size of the input array, then print the subset array and return.
3. If the above condition is false, we have 2 choices.
4. In the first case, we do not include the current element of the input array in the subset. Simple call the recursive function with the next element, the rest of the parameters remain unchanged.
5. In the second case, we include the current element in the subset. Insert the current element of the input array in the subset and call the recursive function with the next element.

#include<iostream>
using namespace std;

// arr: input array
// i: ith index of input array
// n: size of arr
// subset: array to store the subset
// j: current size of subset
void PrintAllSubsets(int *arr, int i, int n,int *subset, int j){	

	// checking if all elements of the array are traverse or not
	if(i==n){
		// print the subset array
		int idx = 0;
		while(idx<j){
			cout<<subset[idx]<<' ';
			++idx;
		}
		cout<<endl;
		return;
	}
	// for each index i, we have 2 options
	// case 1: i is not included in the subset
	// in this case simply increment i and move ahead
	PrintAllSubsets(arr,i+1,n,subset,j);
	// case 2: i is included in the subset
	// insert arr[i] at the end of subset
	// increment i and j
	subset[j] = arr[i];
	PrintAllSubsets(arr,i+1,n,subset,j+1);
		
}

int main()
{
	int arr[] = {1,2,3,4}; // input array
	int subset[100];	   // temporary array to store subset
	int n = 4;
	PrintAllSubsets(arr,0,n,subset,0);   
}


Time Complexity: O(2^N)
Space Complexity: O(N)

Find all subsets of an array using iteration

This method is very simple. It is based on bit-masking. The number of subsets of an array is 2^N where N is the size of the array. We basically generate N-bit binary string for all numbers in the range 0 to 2^N – 1 and print array based on the string. If the ith index of the binary string is 1, that means the ith index of the array is included in the subset.

Steps

1. Set snum = 0.
2. Repeat the following step while snum < 2^N
   • If the ith digit of snum in binary is 1 then it means ith index of input array is included in the subset. If ith digit of snum in binary is 0, then ith index of input array is not included in the subset.
   • Print the input array accordingly.
   • Increment snum.

#include<iostream>
#include<math.h>
using namespace std;

// arr: input array
// n: size of arr
void PrintAllSubsets(int *arr, int n){	

	int snum = 0;
	while(snum<pow(2,n)){
		for(int i=0;i<n;++i){
			// the following condition checks
			// if the ith bit of snum in binary form
			// is 1 or not
			if((snum&(1<<i))!=0){
				cout<<arr[i]<<' ';
			}
		}
		cout<<endl;
		++snum;
	}
			
}

int main()
{
	int arr[] = {1,2,3}; // input array
	int n = 3;
	PrintAllSubsets(arr,n);   
}

Time Complexity: O(2^N)
Space Complexity: O(1)

Read
Right-shift array by 1
Hexadecimal to Decimal
Diamond Pattern Recursive
Matrix Multiplication Recursive