[Algo]:Subset generator

There are three possible solutions to this.

  1. Using DP, cascading.
  2. Backtracking.
  3. Use Bitset method.

DP, cascading solution

use the idea of solving existing solved subset. Like adding a additional number to the existing subset starting with an empty subset”

[]

next number is 1:

[1]

[2]

[1,2]

similarily for other numbers in the array.

Solution:

class Program {
public static List<List<Integer>> powerset(List<Integer> array) {
List<List<Integer>> subsets =new ArrayList<>();
subsets.add(new ArrayList<>());

subset(subsets,array,0 );
return subsets;
}
private static List<List<Integer>> subset(List<List<Integer>> lists,List<Integer> array, int val){

if(val == array.size()){
return lists;
}
List<Integer> temp =null;
List<List<Integer>> res = new ArrayList<>();
for(List list : lists){

temp = new ArrayList<>(list);
temp.add(array.get(val));
res.add(temp);

}
lists.addAll(res);
return subset(lists,array,val+1);

}
}

Backtracking Solution: