Back to Backtracking
Medium
Subsets
Given an integer array `nums` of unique elements, return all possible subsets (the power set). The solution set must not contain duplicate subsets. Return the solution in any order.
Examples
Input:nums = [1,2,3]
Output:[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
All possible combinations of elements from the array are returned.
The empty set is always a subset.
Input:nums = [0]
Output:[[],[0]]
Only the empty set and the single element itself are possible subsets.
Constraints
1 <= nums.length <= 10-10 <= nums[i] <= 10All the numbers of `nums` are unique.
Backtracking (Recursive)
Approach
We can build all subsets by making a choice at each element: either include it in the current subset or exclude it. We use a recursive function that tracks our current position in the array and the current subset we are building. When we reach the end of the array, we add a copy of the current subset to our result.
Complexity Analysis
Time Complexity
O(n * 2^n)
Space Complexity
O(n)
The time complexity is O(n * 2^n) because there are 2^n subsets, and copying each subset takes O(n) time. The space complexity is O(n) for the recursion stack and the `current` array.
Solution.java
class Solution { 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) { // Base case: we've made a decision for every element if (index == nums.length) { result.add(new ArrayList<>(current)); return; } // Decision 1: Include the current element current.add(nums[index]); backtrack(index + 1, nums, current, result); // Decision 2: Exclude the current element // We backtrack by removing the element we just added current.remove(current.size() - 1); backtrack(index + 1, nums, current, result); }}