Given a set of distinct integers, nums, return all possible subsets (the power set).
Note: The solution set must not contain duplicate subsets.
GeeksforGeeks
ProgramCreek
YouTube
Input: nums = [1, 2, 3]
Output: [ [], [1], [2], [3], [1, 2], [1, 3], [2, 3], [1, 2, 3] ]
Last updated
Was this helpful?
Was this helpful?
/**
* 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();
}
}
}