/**
* Time complexity : O(N×2^N) to generate all subsets and then copy
* them into output list.
* Space complexity : O(N×2^N) to keep all the subsets of length N,
* since each of N elements could be present or absent.
*/
class Solution {
public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> resultList = new ArrayList<>();
for(int k = 0; k <= nums.length; k++) {
backtrack(resultList, new LinkedList<Integer>(), nums, 0, k);
}
return resultList;
}
private void backtrack(
List<List<Integer>> resultList,
LinkedList<Integer> currList,
int[] nums,
int start,
int k
) {
if(k == 0) {
resultList.add(new ArrayList(currList));
}
for(int i = start; i < nums.length; i++) {
currList.add(nums[i]);
backtrack(resultList, currList, nums, i+1, k-1);
currList.removeLast();
}
}
}