Generating All Subsets Of An Array In O(2^n)*n Time Complexity
Backtracking approach: exponential time complexity, SC: O(2^n)*(n). Using Bit Manipulation: TC: O(2^n)*n, SC: O(2^n)*n. Generate subsets by considering bit values in nums[].
Problem
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>...