How to find all the subsets of a given List(or Collection): Part 1

Today I am going to share the algorithm of how to generate all the subsets from a given Collection. For example, if the given collection is an int array [1,2,3], then its subsets are [[1], [2],[3],[1,2],[1,3],[2,3],[1,2,3]]. First of all, let’s look at the first few examples.

Basically, if there are n elements in the given collection, we will have n^2-1 subsets because we do not consider empty subset [] here.

As you can observe from the table above, subsets of [1,2] is to append [2] to the subsets of [1] along with a [2]. And subsets of [1,2,3] is to append 3 to each subset of [1,2]’s subsets along with a single [3]. To formally describe this process, we denote S([1]) as the subsets of [1], then we can get

S([1,2])=Σ([2]+S([1])[i]) + [2]

This is very similar to the string permutation problem except in the permutation problem, each resulting String has identical length as the source where it is not true in this case.

The analysis above suggests a straightforward recursive solution which is to recursively find the subsets of [1...n-1], then apply the manipulation mentioned above. So here is the recursive solution.

	public static <T> List<Set<T>> getSubsets(List<T> list){
		if(list==null || list.size()==0)
			throw new IllegalArgumentException("Given set should not be null");
		List<Set<T>> result = new ArrayList<Set<T>>();
		/**
		 * If there is only one element in the list, return a List with only one set
		 */
		if(list.size()==1){
			Set<T> set = new HashSet<T>();
			set.addAll(list);
			result.add(set);
			return result;
		}
		/**
		 * Construct a new list which contains element 0 to n-1
		 */
		List<T> newList = new ArrayList<T>();
		for(int i=0; i<list.size()-1; i++){
			newList.add(list.get(i));
		}
		/**
		 * Get the subsets of the new list
		 */
		List<Set<T>> temp = getSubsets(newList);
		int size = temp.size();
		/**
		 * Append element n to each subsets and add it to the final list
		 */
		for(int i=0; i<size; i++){
			Set<T> s = temp.get(i);
			Set<T> local = new HashSet<T>();
			local.addAll(s);
			local.add(list.get(list.size()-1));
			temp.add(local);
		}
		/**
		 * Add element n itself to the subsets
		 */
		Set<T> set = new HashSet<T>();
		set.add(list.get(list.size()-1));
		temp.add(set);
		result.addAll(temp);
		return result;
	}

As you might wonder, in this case, it has a huge overhead to apply a recursive approach because the running time of this algorithm is n! which also implies that this problem is NP-hard. Intuitively, using an iterative approach should be able to eliminate the overhead. However, as I’ve tried, the main problem is not the time complexity but the space(Nevertheless, my another approach is better than this one in terms of a iterative approach and a little pruning). My computer can only handle around 16!(=20 922 789 888 000) subsets store in memory. As a result, no matter we are using a recursive or iterative approach, if you need to store all the subsets, you better replace your computer.

Clap

Clap