C++ Programming Code Examples

C++ > Sorting Searching Code Examples

Implement the Binary Counting Method to Generate Subsets of a Set



Implement the Binary Counting Method to Generate Subsets of a Set

- This algorithm print all the possible combination of each length from the given array using binary counting method.
- The time complexity of this algorithm is O(n*(2^n)).

- This algorithm takes the input of 'n' data element and prints all possible combination.
- For that, it generates n bit binary number from 0 to 2^n.
- For each number, it prints an unique combination.
- Exit.

#include<iostream>
#include<math.h>
 
using namespace std;
 
// A function to print array element according to the code in the argument list.
void print(char code[], int arr[], int n)
{
	int i;
	cout<<"\t{ ";
	for(i = 0; i < n; i++)
	{
		// Print if the corresponding value is '1'.
		if(code[i] == '1')
			cout<<arr[i]<<" ";
	}
	cout<<"}\n";
}
 
// A function to generate subset by binary counting.
int BinaryCounting(int arr[], int n)
{
	int r, i, l;
	char binary[] = "0000";
	r = pow(2, n);
 
	for(i = 0; i < r; i++)
	{
		print(binary, arr, n);
		l=n-1;
 
		// Incrementing the binary value with each iteration.
		h:
		if(binary[l] == '0')
			binary[l] = '1';
		else
		{
			binary[l] = '0';
			l--;
			goto h;
		}
	}
}
 
int main()
{
	int i, n;
	cout<<"\nEnter the number of element array have: ";
	cin>>n;
 
	int arr[n];
	cout<<"\n";
 
	// Take the input of the array.
	for(i = 0; i < n; i++)
	{
		cout<<"Enter "<<i+1<<" element: ";
		cin>>arr[i];
	}
 
	// Print the subset using binary counting method.
	cout<<"\nThe subset in the binary counting method: \n";
	BinaryCounting(arr, n);
 
	return 0;
}