-1

I'm trying to write code to output all subsets of a set (represented by a list of integers). Why doesn't the following code work?

public static List<List<Integer>> powerSet(List<Integer> l){
    List<List<Integer>> result = new ArrayList<List<Integer>>();
    if (l.size() == 0) {
        result.add(new ArrayList<>());
    }
    else { 
        List<List<Integer>> prev = powerSet(l.subList(0, l.size() - 1));
        for (List<Integer> x : prev) {
            x.add(l.get(l.size() - 1));
            result.add(x);
        }
    }
    return result;
}

My thinking is that to compute the subsets of a set A[0...n-1] of size n, we can just add the last element A[n - 1] of the set to the subsets of A[0...n-2]. However, the code above only gives me the same set:

public static void main(String[] args) {

    List<Integer> l = new ArrayList<>();
    l.add(0);
    l.add(1);
    l.add(2);

    List<List<Integer>> result = powerSet(l);

    System.out.println(result.toString());
}
dxjuv
  • 879
  • 1
  • 8
  • 28
medihde
  • 21
  • 7
  • 2
    Please see [ask], and edit your question to include a [mcve] including full details of the input, expected result and actual result. – kaya3 Feb 24 '20 at 02:43
  • [What is a debugger and how can it help me diagnose problems?](https://stackoverflow.com/q/25385173/5221149) --- Or you could just add print statements and the problem should quickly show itself, e.g. print the value of `l` on entry to the method, and print the value of `result` right before returning. – Andreas Feb 24 '20 at 03:41
  • Sorry, I've edited my post – medihde Feb 24 '20 at 10:31

1 Answers1

1

You could convert it to binary? E.g. if you have 3 elements then all the possible answers will be contained in:

000
001
010
011
100
101
110
111

So 1 = element present, 0 = element missing

So you just have a loop starting at 0 and < 2^n

The i^th element is determined by taking 2 and raising it to the power of i.

(NB: 2^0 = 1, 2^1 = 2, 2^2 = 4 etc.)

Rick
  • 576
  • 3
  • 12