The best programs are written so that computing machines can perform them quickly and so that human beings can understand them clearly. A programmer is ideally an essayist who works with traditional aesthetic and literary forms as
well as mathematical concepts, to communicate the way that an algorithm works and to convince a reader that the results will be correct. Donald E. Knuth

Miscellaneous

Problem :-
Given a set with 'n' elements, print subsets of all possible sizes.
Suppose we are given a set { 1, 2, 3 }
Possible subsets :: { 1 }  |  { 1, 2 }  |  { 1, 2, 3 }  |  { 1, 3 }  |  { 2 }  |  { 2, 3 }  |  { 3 }  |  { }

Solution :-
We will iterate over the set elements and find out all possible subsets recursively with the current set element as the first element of the subsets. Once the iteration of the set is over, we have found different subsets starting with each set element. See the implementation below.

#include<iostream>
using namespace std;

// print the subset
void printSet(int set[],int size) {
   cout<<"\n{ ";
   int i;
   for(i=0;i<size;i++) {
      cout<<set[i];
      if (i < size) {
         cout<<",";
      }
   }
   cout<<" }";
}

// recursively compute subset elements for subsets of all possible sizes 
void subsets(int set[],int start,int end,int subset[],int index) {
   printSet(subset,index);
   int i;
   for(i=start;i<=end;i++) {
      subset[index] = set[i];
      subsets(set,start+1,end,subset,index+1);
      start += 1;
   }
}

// generate subsets of all sizes
void generateSubsets(int set[],int size) {
   int i,j;
   int subset[size]; //stores the subset elements
   for(i=0;i<size;i++) {
      int start = i+1;
      int end = size-1;
      // first element is the current index
      subset[0] = set[i];
      // compute other elements of all the subsets with first element as set[i]      
      subsets(set,start,end,subset,1);
   }
   // print the NULL set
   cout<<"\n{ }";
}

// main
int main() {
   int set[] = {1,2,3,4};
   int size = sizeof(set)/sizeof(set[0]);
   cout<<"\nAll possible subsets are :-\n";
   generateSubsets(set,size);
   cout<<endl;
}

Back | Next

All Miscellaneous Problems
* Print all possible permutation of array elements
* Given the number of parenthesis pairs, print all possible combination of Balanced Parenthesis
* Given a set with 'n' elements, print subsets of all possible sizes
* Given a triangle in the form of a lower diagonal matrix, find the weight of maximum path in the triangle
* Given a matrix of 0s & 1s, find the maximum size square submatrix with all values as 1
* Given a set with 'n' elements. Find the sum of maximum elements in all subsets of size 'p' such that p <= n
* Given 2 strings, find all possible interleaved combination of the characters of the 2 strings