Calculating all of the subsets of a set of numbers

Your code is really confusing and there is no explanation.

You can do iteratively with a bitmask that determines which numbers are in the set. Each number from 0 to 2^n gives a unique subset in its binary representation, for example

for n = 3:

i = 5 -> 101 in binary, choose first and last elements i = 7 -> 111 in binary, choose first 3 elements

Suppose there are n elements (n < 64, after all if n is larger than 64 you'll run that forever).

for(long i = 0; i < (1<<n); i++){
    ArrayList<Integer> subset = new ArrayList<Integer>();
    for(int j = 0; j < n; j++){
        if((i>>j) & 1) == 1){ // bit j is on
            subset.add(numbers.get(j));
        }
    }
    // print subset
}

Just a primer how you could solve the problem:

Approach 1

• Take the first element of your number list
• generate all subsets from the remaining number list (i.e. the number list without the chosen one) => Recursion!
• for every subset found in the previous step, add the subset itself and the subset joined with the element chosen in step 1 to the output.

Of course, you have to check the base case, i.e. if your number list is empty.

Approach 2

It is a well known fact that a set with n elements has 2^n subsets. Thus, you can count in binary from 0 to 2^n and interpret the binary number as the corresponding subset. Note that this approach requires a binary number with a sufficient amount of digits to represent the whole set.

It should be a not too big problem to convert one of the two approaches into code.

What you want is called a Powerset. Here is a simple implementation of it:

public static Set<Set<Integer>> powerSet(Set<Integer> originalSet) {
        Set<Set<Integer>> sets = new HashSet<Set<Integer>>();
        if (originalSet.isEmpty()) {
            sets.add(new HashSet<Integer>());
            return sets;
        }
        List<Integer> list = new ArrayList<Integer>(originalSet);
        Integer head = list.get(0);
        Set<Integer> rest = new HashSet<Integer>(list.subList(1, list.size()));
        for (Set<Integer> set : powerSet(rest)) {
            Set<Integer> newSet = new HashSet<Integer>();
            newSet.add(head);
            newSet.addAll(set);
            sets.add(newSet);
            sets.add(set);
        }
        return sets;
    }

I will give you an example to explain how the algorithm works for the powerset of {1, 2, 3}:

• Remove {1}, and execute powerset for {2, 3};
  • Remove {2}, and execute powerset for {3};
    • Remove {3}, and execute powerset for {};
      • Powerset of {} is {{}};
    • Powerset of {3} is 3 combined with {{}} = { {}, {3} };
  • Powerset of {2, 3} is {2} combined with { {}, {3} } = { {}, {3}, {2}, {2, 3} };
• Powerset of {1, 2, 3} is {1} combined with { {}, {3}, {2}, {2, 3} } = { {}, {3}, {2}, {2, 3}, {1}, {3, 1}, {2, 1}, {2, 3, 1} }.