Best way to get a power set of an array?

Question

What is the best way to get the power set of an array? For example if I have an array:

int[] A = {1, 2}

And to get the following output

int[] P = {{}, {1}, {2}, {1, 2}}

I don't think this is a duplicate. For some use cases, we might not want to convert our array to a Set. The proposed solution for this question is faster than the set solution. — Simon Baars, May 15 '19 at 15:31

score 1 · Accepted Answer · answered Oct 23 '16 at 09:41

1

Try this.

int[] a = {1, 2};
int max = 1 << a.length;
int[][] result = new int[max][];
for (int i = 0; i < max; ++i) {
    result[i] = new int[Integer.bitCount(i)];
    for (int j = 0, b = i, k = 0; j < a.length; ++j, b >>= 1)
        if ((b & 1) != 0)
            result[i][k++] = a[j];
}
System.out.println(Arrays.deepToString(result));

result:

[[], [1], [2], [1, 2]]

answered Oct 23 '16 at 09:41

Thank you so much. – Michael Oct 23 '16 at 09:48

Best way to get a power set of an array?

1 Answers1