Scale Engineer

Subsets

Med
#0078Time: O(n * 2^n)Space: O(n * 2^n)20 companies
Patterns
BacktrackingBit Manipulation
Data structures
Array
Companies
AdobeAmazonAppleBloomberg

Prompt

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]]

 

Constraints:

  • 1 <= nums.length <= 10
  • -10 <= nums[i] <= 10
  • All the numbers of nums are unique.

Approaches

3 approaches with complexity analysis and trade-offs.

This approach builds the solution iteratively. It starts with an empty subset in the result list. Then, it iterates through each number in the input array. For each number, it goes through all the subsets currently in the result list, creates a new subset by adding the current number to each of them, and adds these new subsets to the result list.

Algorithm

  • Initialize a list of lists result and add an empty list to it.
  • For each number num in the input array nums:
    • Get the current number of subsets in result.
    • Iterate through the existing subsets (from index 0 to the original size).
    • For each existing subset, create a new subset by copying it and adding num.
    • Add this new subset to the result list.
  • Return result.

Walkthrough

The algorithm begins by initializing the result list with just the empty set. It then iterates through each number in the input nums array. In each iteration, it effectively doubles the number of subsets in the result list. It does this by iterating through the subsets that have been computed so far, and for each one, it creates a new subset that is a copy of the existing one plus the current number. These newly formed subsets are then added to the result list.

For example, with nums = [1, 2]:

  1. Start with result = [[]].
  2. Process 1: Create a new subset [1] from []. Add it. result is now [[], [1]].
  3. Process 2: Create new subsets [2] (from []) and [1, 2] (from [1]). Add them. result is now [[], [1], [2], [1, 2]].
class Solution {    public List<List<Integer>> subsets(int[] nums) {        List<List<Integer>> result = new ArrayList<>();        result.add(new ArrayList<>()); // Start with the empty set         for (int num : nums) {            int currentSize = result.size();            for (int i = 0; i < currentSize; i++) {                // Create a new subset from an existing one and add the current number                List<Integer> newSubset = new ArrayList<>(result.get(i));                newSubset.add(num);                result.add(newSubset);            }        }        return result;    }}

Complexity

Time

O(n * 2^n)

Space

O(n * 2^n)

Trade-offs

Pros

    • Intuitive and easy to understand.
    • Avoids recursion, so there's no risk of stack overflow.

Cons

    • Can be less performant due to the overhead of creating many new list objects and copying elements in each step.

Solutions

class Solution {private  List<List<Integer>> ans = new ArrayList<>();private  List<Integer> t = new ArrayList<>();private  int[] nums;public  List<List<Integer>> subsets(int[] nums) {    this.nums = nums;    dfs(0);    return ans;  }private  void dfs(int i) {    if (i == nums.length) {      ans.add(new ArrayList<>(t));      return;    }    dfs(i + 1);    t.add(nums[i]);    dfs(i + 1);    t.remove(t.size() - 1);  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem