Here is the code we wrote today:

import java.util.*;

public class Subsets {

	public static int subsets(int n) {
		//returns # of subsets of numbers 1 through n (inclusive)
		if(n == 0)
			return 1;
		int withoutN = subsets(n-1);
		int withN = subsets(n-1);
		return withoutN + withN;
	}
	
	public static void main(String[] args) {
		//System.out.println(subsets(4));
		printSubsets(4, new LinkedList());
	}

	public static void printSubsets(int n, LinkedList< Integer> alsoPrint) {
		//prints subsets of numbers 1..n, each with the contents of alsoPrint

		if(n == 0) {
			for(Integer i : alsoPrint)
				System.out.print(i + " ");
			System.out.println();
		} else {
			printSubsets(n-1, alsoPrint);  //print subsets of 1..n-1

			//print them again, but add n to each
			alsoPrint.addFirst(n);	
			printSubsets(n-1, alsoPrint);
			alsoPrint.removeFirst();
		}
	}
}