Constructing All Subsets - Backtracking | The Algorithm Design Manual

AbstractSubsetsGenerator.java

package backtracking_subsets;

import static org.junit.Assert.assertEquals;
import static org.junit.Assert.assertNotNull;
import static org.junit.Assert.assertTrue;

import java.util.LinkedList;
import java.util.List;
import java.util.Set;
import java.util.TreeSet;

import org.junit.Before;
import org.junit.Test;

public abstract class AbstractSubsetsGenerator implements SubsetsGenerator {

	private SubsetsGenerator solution;

	@Before
	public void setUp() throws Exception {
		final Class<? extends SubsetsGenerator> klass = getClass();
		solution = klass.newInstance();
	}

	@Test(timeout = 2000)
	public void empty() {
		List<Set<Integer>> subsets = solution.subsets(new int[] {});

		assertNotNull(subsets);
		assertEquals(1, subsets.size());
	}

	@Test(timeout = 2000)
	public void oneElement() {
		List<Set<Integer>> subsets = solution.subsets(new int[] { 1 });
		assertNotNull(subsets);

		subsets = new LinkedList<Set<Integer>>(subsets);
		assertEquals(2, subsets.size());
		assertListContainsSubset(subsets);
		assertListContainsSubset(subsets, 1);
	}

	@Test(timeout = 2000)
	public void twoElement() {
		List<Set<Integer>> subsets = solution.subsets(new int[] { 1, 2 });

		assertNotNull(subsets);
		subsets = new LinkedList<Set<Integer>>(subsets);
		assertEquals(4, subsets.size());
		assertListContainsSubset(subsets);
		assertListContainsSubset(subsets, 1);
		assertListContainsSubset(subsets, 2);
		assertListContainsSubset(subsets, 1, 2);
	}

	@Test(timeout = 2000)
	public void threeElement() {
		List<Set<Integer>> subsets = solution.subsets(new int[] { 1, 2, 3 });

		assertNotNull(subsets);
		subsets = new LinkedList<Set<Integer>>(subsets);
		assertEquals(8, subsets.size());
		assertListContainsSubset(subsets);
		
		assertListContainsSubset(subsets, 1);
		assertListContainsSubset(subsets, 2);
		assertListContainsSubset(subsets, 3);
		
		assertListContainsSubset(subsets, 1, 2);
		assertListContainsSubset(subsets, 1, 3);
		assertListContainsSubset(subsets, 2, 3);
		
		assertListContainsSubset(subsets, 1, 2, 3);
	}

	private static void assertListContainsSubset(
			List<Set<Integer>> subsets,
			int... ns)
	{
		final Set<Integer> set = new TreeSet<Integer>();
		for (int i : ns)
			set.add(i);
		assertTrue(set.toString(), subsets.contains(set));
	}

}

BinaryCountingSubsets.java

package backtracking_subsets;

import java.util.LinkedList;
import java.util.List;
import java.util.Set;
import java.util.TreeSet;

/**
 * Binary counting - The simplest approach to subset generation problems
 */
public class BinaryCountingSubsets extends AbstractSubsetsGenerator {

	public List<Set<Integer>> subsets(int[] items) {
		if (items.length > 63) throw new IllegalArgumentException();
		
		final List<Set<Integer>> subsetList = new LinkedList<Set<Integer>>();
		final long max = (long)Math.pow(2, items.length);
		
		for (long n = 0; n < max; n++) {
			Set<Integer> subset = new TreeSet<Integer>();
			for (int i = 0; i < items.length; i++)
				if ((n&(1<<i)) != 0)
					subset.add(items[i]);
			subsetList.add(subset);
		}
		return subsetList;
	}

}

DFSSubsets.java

package backtracking_subsets;

import java.util.LinkedList;
import java.util.List;
import java.util.Set;
import java.util.TreeSet;

public class DFSSubsets extends AbstractSubsetsGenerator {

	private List<Set<Integer>> subsetList = new LinkedList<Set<Integer>>();

	private void subsets_dfs(int[] items, Set<Integer> subset, int k) {
		if (k == items.length) {
			//System.out.println(subset);
			subsetList.add(new TreeSet<Integer>(subset));
		} else {
			for (int b = 1; b >= 0; b--) {
				if (b != 0) subset.add(items[k]);
				subsets_dfs(items, subset, k + 1);
				subset.remove(items[k]);
			}
		}
	}

	public List<Set<Integer>> subsets(int[] items) {
		subsets_dfs(items, new TreeSet<Integer>(), 0);
		return subsetList;
	}


}

SubsetsGenerator.java

package backtracking_subsets;

import java.util.List;
import java.util.Set;

/**
 * Constructing All Subsets - Backtracking | The Algorithm Design Manual
 */
public interface SubsetsGenerator {

	public List<Set<Integer>> subsets(int[] items);

}