# Generating all subsets of a given set

I am learning Java Collections Framework. Can someone look at this code for generating all subsets of a given set and tell me any issues with it.

import java.util.*;
public class AllSubsets {
public static void main(String[] args) {
Set<Integer> original = new HashSet<Integer>();
for (int i = Integer.parseInt(args[0]); i > 0; i--) {
}
System.out.println(generateAllSubsets(original));
}

public static HashSet<HashSet<Integer>> generateAllSubsets(Set<Integer> original) {

HashSet<HashSet<Integer>> allSubsets = new HashSet<HashSet<Integer>>();

Iterator it = original.iterator();
while(it.hasNext()) {
Integer element = (Integer) it.next();

//Deep copy all subsets to temporary power set.
HashSet<HashSet<Integer>> tempClone = new HashSet<HashSet<Integer>>();
for (HashSet<Integer> subset : allSubsets) {
}

//All element to all subsets of the temporary power set.
Iterator it2 = tempClone.iterator();
while(it2.hasNext()) {
Set<Integer> s = (HashSet<Integer>) it2.next();
}

//Merge both power sets.
}
return allSubsets;
}
}

• you use vague algorithm, so no one wish to decrypt and and thus you received no answer. To represent a subset, usually an integer in binary representation is used: 0 in a given position means element is absent, 1 - present. To generate all subsets, start with 0 and add 1, counting all integers up to 2^N-1. If you have less than 64 elements, you can use long integer, other wise use BitSet, and implement operation of adding 1. – Alexei Kaigorodov Oct 6 '12 at 17:47
• @AlexeiKaigorodov, how can an implementation in an actual language be a "vague algorithm"? Pseudocode can be vague, but this isn't. – Peter Taylor Oct 6 '12 at 17:48
• Guava has same kind of method and check also in SO – Anirban Nag 'tintinmj' Jan 2 '14 at 20:17

The first, obvious, issue is that generating the set in memory uses a lot of memory. However, making a lazy version is a bit more advanced, so don't worry about it for now.

### 1. Code to the interface, not the implementation

public static HashSet<HashSet<Integer>> generateAllSubsets(Set<Integer> original) {


public static Set<Set<Integer>> generateAllSubsets(Set<Integer> original) {


is better.

### 2. Generics reduce repetition

public static <T> Set<Set<T>> generateAllSubsets(Set<T> original) {


is better still, because you can use it to find power sets of any set.

### 3. Generics remove the necessity to do most casts

    Iterator it = original.iterator();
while(it.hasNext()) {
Integer element = (Integer) it.next();


and

        Iterator it2 = tempClone.iterator();
while(it2.hasNext()) {
Set<Integer> s = (HashSet<Integer>) it2.next();


have wholly unnecessary explicit casts (which in the second case generates a warning) because you're using the raw type Iterator. Both can also be simplified using the same foreach syntax which you use when making the copy of the power set so far.

### 4. KISS

You have three loops (including the one hidden behind allSubsets.addAll), which seems to me to be unnecessarily complicated. If you make a shallow copy first then you can combine the deep copy with the adding an element.

public static <T> Set<Set<T>> generateAllSubsets(Set<T> original) {
Set<Set<T>> allSubsets = new HashSet<Set<T>>();

for (T element : original) {
// Copy subsets so we can iterate over them without ConcurrentModificationException
Set<Set<T>> tempClone = new HashSet<Set<T>>(allSubsets);

// All element to all subsets of the current power set.
for (Set<T> subset : tempClone) {
Set<T> extended = new HashSet<T>(subset);

You'll note that I'm using the copy-constructor rather than clone(). That's a matter of taste: fundamentally there's no real difference, because they're both special-cased.