PROBLEM DESCRIPTION
For a given list of numbers, return the list of its power set.
SOLUTION
APPROACH 1
This can be solved recursively. We call the function twice, once assuming that the current element i will be included in the Power Set and the second time when it will not be included in the Power Set.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
import java.util.*;
class Program {
static List<List<Integer>> output = new ArrayList<>();
public static void powerset(List<Integer> array, int i, List<Integer> current) {
if(i==array.size()){
output.add(new ArrayList<>(current));
return;
}
//excluding
powerset(array, i+1, new ArrayList<>(current));
//including
List<Integer> temp = new ArrayList<>(current);
temp.add(array.get(i));
powerset(array, i+1, temp);
}
public static List<List<Integer>> powerset(List<Integer> array) {
output = new ArrayList<>();
powerset(array, 0, new ArrayList<Integer>());
return output;
}
}
APPROACH 2
This is a better approach and it uses iterative way to solve this problem. To the output list, we add [] since it will be present for any given list. Next, we take the elements in the given list one by one and include them in all the elements in our current output list.
Example
Initialization:
{[]}After first element:
{[][1]}After second element:
{[][1][2][1,2]}After third element:
{[][1][2][1,2][3][1,3][2,3][1,2,3]}
In the second loop, take the size of the output array first instead of doing something like for(int j=0; j<output.size(); j++) because the size of the output array will keep increasing as we add more elements to it.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
import java.util.*;
class Program {
public static List<List<Integer>> powerset(List<Integer> array) {
List<List<Integer>> output = new ArrayList<>();
output.add(new ArrayList<>());
for(int i=0; i<array.size(); i++){
int x = array.get(i);
int n = output.size();
for(int j=0; j<n; j++){
List<Integer> temp = new ArrayList<>(output.get(j));
temp.add(x);
output.add(temp);
}
}
return output;
}
}