Photo by Artem Shuba on Unsplash
Subsets - Leetcode
Finding subsets of an array using bit manipulation(Power Set) and recursion.
Table of contents
Bit Manipulation
public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
int len = nums.length;
for(int n = 0; n < Math.pow(2, len); n++) {
List<Integer> curList = new ArrayList<>();
for(int i = 0; i < len; i++) {
if( (n & (1 << i)) != 0 )
curList.add(nums[i]);
}
res.add(curList);
}
return res;
}
Recursion
public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
f(res, 0, new ArrayList<>(), nums);
return res;
}
private void f(List<List<Integer>> res, int ind, List<Integer> arr, int[] nums) {
if(nums.length == ind) {
res.add(new ArrayList<>(arr));
System.out.println(arr);
return;
}
arr.add(nums[ind]);
f(res, ind+1, arr, nums);
arr.remove(arr.size() - 1);
f(res, ind+1, arr, nums);
}