Backtracking approach:
TC:(2^n) i.e. exponential time complexity (Since we are left with two choice at every recursive call i.e. either to consider the value at 'index' or not that leads to 2 possible outcome, this will happen for n times)
SC:(2^n)*(n), n for temp ArrayList<>() and 2^n for the main ArrayList<>();
class Solution {
public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> list = new ArrayList<>();
powerSet(nums,0,list,new ArrayList<Integer>());
return list;
}
public void powerSet(int [] nums, int index , List<List<Integer>> list, List<Integer> l){
//base case
if(index ==nums.length){
list.add(new ArrayList<>(l));
return;
}
//take
l.add(nums[index]); //consider the value at 'index'
powerSet(nums,index+1,list,l);
//dont take;
l.remove(l.size()-1);// don't consider the value at 'index'
powerSet(nums,index+1,list,l);
}
}
Using Bit Manipulation:
TC: O(2^n)*n
SC: O(2^n)*n, (2^n for the main list, and n for the subset lists, well not all the subsets will be of size n but still we can assume that is the case)
pre-requisite: check if ith bit is set or not ( refer the Bit manipulation tips and tricks page for more details)
Intuition:
If all the no . subsets are represented as binary values,
for example : if n = 3 i.e. array having 3 value in it.
there will be 2^n = 8 subsets
8 subsets can also be represented as
| index 2 | index 1 | index 0 | subset number |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 |
| 0 | 1 | 0 | 2 |
| 0 | 1 | 1 | 3 |
| 1 | 0 | 0 | 4 |
| 1 | 0 | 1 | 5 |
| 1 | 1 | 0 | 6 |
| 1 | 1 | 1 | 7 |
We will take into consideration that if bit value is 1 then that index value in the nums[] should be taken into consideration for forming the subset.
This way we will be able to create all the subsets
class Solution {
public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> list = new ArrayList<>();
int n = nums.length;
int noOfSubset = 1<<n; // this is nothing but 2^n, i.e if there are n elements in the array, they will form 2^n subsets
for(int num = 0;num<noOfSubset;num++){ /// all possible subsets numbers
List<Integer> l = new ArrayList<>();
for(int i =0;i<n;i++){// for the given subset number find which index value to pick
if((num & (1<<i))!=0) l.add(nums[i]);
}
list.add(l);
}
return list;
}
}
Top comments (0)