Subsets
Given an integer array nums of unique elements, return all possible subsets (the power set). The solution set must not contain duplicate subsets. It is guaranteed that 0 <= nums.length <= 10.
Constraints:
- 1 <= nums.length <= 10
- All elements in nums are unique
Examples:
Input: [1, 2, 3]
Output: [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]
Explanation: The subsets of [1, 2, 3] are all possible subsets, including the empty subset and the subset containing all elements.
Solutions
Backtracking
Time: O(2^n)Space: O(2^n)
The backtracking approach generates all possible subsets by adding each element to the current subset and then recursively generating all subsets of the remaining elements.
public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
backtrack(res, new ArrayList<>(), nums, 0);
return res;
}
private void backtrack(List<List<Integer>> res, List<Integer> tempList, int[] nums, int start) {
res.add(new ArrayList<>(tempList));
for (int i = start;
i < nums.length;
i++) {
tempList.add(nums[i]);
backtrack(res, tempList, nums, i + 1);
tempList.remove(tempList.size() - 1);
}
}Follow-up:
Generate all possible subsets of a given array of integers, where each integer can be used more than once.
