class genSubsets{

	public static void genSubsets(int n)
	{
		// We use a boolean array of size n to represent
		// subsets of {1, 2, .., n}. If the jth slot is
		// true that means j+1 is in the subset. If the
		// jth slot is false, it means j+1 is not in the
		// subset.
		boolean[] subset = new boolean[n];
		recursiveGenSubsets(n, subset);
	}

	public static void recursiveGenSubsets(int n, boolean[] subset)
	{

		// base case: when n gets to 0, it indicates that
		// a subset has been completely generated and it is
		// time to print it out
		if(n == 0)
		{
			printSubset(subset);
			return;
		}
	
		// There are two recursive cases.

		// First generate all subsets containing n.
		// This is done by setting the nth element true
		// and generating all subsets of the first n-1 elements
		subset[n-1] = true;
		recursiveGenSubsets(n-1, subset);

		// Then generate all subsets not containing n.
		// This is done by setting the nth element false
		// and generating all subsets of the first n-1 elements
		subset[n-1] = false;
		recursiveGenSubsets(n-1, subset);
	}

	public static void printSubset(boolean[] subset)
	{
		boolean emptySet = true;
		for(int j = 0; j < subset.length; j++)
			if(subset[j])
				emptySet = false;

		if(emptySet)
		{
			System.out.println("Empty set");
			return;
		}

		for(int j = 0; j < subset.length; j++)
			if(subset[j])
			{
				System.out.print(j+1);
				System.out.print(" ");
			}
		System.out.println();
	}

        public static void main(String[] args)
        {
                genSubsets(5);
        }

}