Calculating all of the subsets of a set of numbers

Question

I want to find the subsets of a set of integers. It is the first step of "Sum of Subsets" algorithm with backtracking. I have written the following code, but it doesn't return the correct answer:

BTSum(0, nums); ///************** ArrayList<Integer> list = new ArrayList<Integer>();  public static ArrayList<Integer> BTSum(int n, ArrayList<Integer> numbers) {     if (n == numbers.size()) {         for (Integer integer : list) {             System.out.print(integer+", ");         }         System.out.println("********************");         list.removeAll(list);         System.out.println();     } else {         for (int i = n; i < numbers.size(); i++) {             if (i == numbers.size() - 1) {                 list.add(numbers.get(i));                 BTSum(i + 1, numbers);             } else {                 list.add(numbers.get(i));                 for (int j = i+1; j < numbers.size(); j++)                 BTSum(j, numbers);             }         }     }      return null; } 

For example, if I want to calculate the subsets of set = {1, 3, 5} The result of my method is:

 1, 3, 5, ********************   5, ********************   3, 5, ********************   5, ********************   3, 5, ********************   5, ******************** 

I want it to produce:

1, 3, 5  1, 5 3, 5 5 

I think the problem is from the part list.removeAll(list); but I dont know how to correct it.

Answer 1

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} }.

Answer 2

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.