78. 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.

Example 1:

Input: nums = [1,2,3]
Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

Example 2:

Input: nums = [0]
Output: [[],[0]]

 1class Solution {
 2
 3  public List<List<Integer>> subsets(int[] nums) {
 4    List<List<Integer>> allSubsets = new ArrayList<>();
 5    dfs(nums, 0, new ArrayList<>(), allSubsets);
 6    return allSubsets;
 7  }
 8
 9  private void dfs(
10    int[] nums,
11    int start,
12    List<Integer> currentSubset,
13    List<List<Integer>> allSubsets
14  ) {
15    allSubsets.add(new ArrayList<>(currentSubset));
16    for (int i = start; i < nums.length; ++i) {
17      currentSubset.add(nums[i]);
18      dfs(nums, i + 1, currentSubset, allSubsets);
19      currentSubset.remove(currentSubset.size() - 1);
20    }
21  }
22}

Call stack for input [1, 2, 3]

>> dfs(start: 0, currentSubset: [])
    >> dfs(start: 1, currentSubset: [1])
        >> dfs(start: 2, currentSubset: [1, 2])
            >> dfs(start: 3, currentSubset: [1, 2, 3])
        >> dfs(start: 3, currentSubset: [1, 3])
    >> dfs(start: 2, currentSubset: [2])
        >> dfs(start: 3, currentSubset: [2, 3])
    >> dfs(start: 3, currentSubset: [3])

Time Complexity

Space Complexity

\(\mathcal{O}(2^n)\)

\(\mathcal{O}(2^n)\)