Problem
Given an integer array nums containing unique elements, return all possible subsets of the array. The solution set must not contain duplicate subsets, and the subsets may be returned in any order.Example(s)
Consider the following example(s) to understand the expected input and output.Input
nums = [1,2,3]
Output
[[],[1],[2],[1,2],[1,3],[2,3],[1,2,3]] Solution
This solution uses Backtracking to generate every possible subset. For each element, we have two choices: include it in the current subset or exclude it.Starting with an empty subset, we add the current subset to the result at every recursive step. We then try adding each remaining element and recursively continue building larger subsets.
After each recursive call, the last element is removed so that the same list can be reused to explore the next possible subset.
public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
backtrack(0, nums, new ArrayList<>(), result);
return result;
}
private void backtrack(int index, int[] nums, List<Integer> current,
List<List<Integer>> result) {
// All elements have been processed.
if (index == nums.length) {
result.add(new ArrayList<>(current));
return;
}
// Choose the current element.
current.add(nums[index]);
backtrack(index + 1, nums, current, result);
// Undo the choice.
// Skip the current element.
current.remove(current.size() - 1);
backtrack(index + 1, nums, current, result);
}
Complexity
For an array containing n elements, there are2n possible subsets. Creating and storing all subsets requires O(n × 2n) time in the worst case.
The recursive call stack and the current subset require
O(n) extra space, excluding the space required for the output.