Back to DSA
Subsets
mediumGiven an array of distinct integers, enumerate every possible subset (the power set). The output must not contain duplicate subsets and may be listed in any order.
Examples
Example 1:
Input:
nums = [4,5,6]Output:
[[],[4],[5],[4,5],[6],[4,6],[5,6],[4,5,6]] Example 2:
Input:
nums = [1]Output:
[[],[1]]Hints
import java.util.*;
class Solution {
public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
backtrack(nums, 0, new ArrayList<>(), result);
return result;
}
private void backtrack(int[] nums, int start, List<Integer> current, List<List<Integer>> result) {
result.add(new ArrayList<>(current));
for (int i = start; i < nums.length; i++) {
current.add(nums[i]);
backtrack(nums, i + 1, current, result);
current.remove(current.size() - 1);
}
}
}Time complexity
O(n * 2^n)Space complexity
O(n)