Skip to main content

78. Subsets

mediumAsked at Airbnb

Generate every combination of amenities a listing can offer — Airbnb's search filter engine enumerates amenity subsets to build exhaustive filter option sets for features like pool plus wifi plus kitchen on the host settings page.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

Given an integer array nums of unique elements, return all possible subsets (the power set). The solution set must not contain duplicate subsets and may be returned in any order.

Constraints

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

Examples

Example 1

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

Explanation: The power set of [1,2,3] has 2^3 = 8 subsets including the empty set.

Example 2

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

Approaches

1. Backtracking (DFS)

Recursively build subsets by choosing to include or exclude each element. At every index, add the current subset to results then recurse with each remaining element.

Time
O(2^n * n)
Space
O(n)
function subsets(nums) {
  const result = [];
  function dfs(start, current) {
    result.push([...current]);
    for (let i = start; i < nums.length; i++) {
      current.push(nums[i]);
      dfs(i + 1, current);
      current.pop();
    }
  }
  dfs(0, []);
  return result;
}

Tradeoff:

2. Iterative bit masking

For n elements there are 2^n subsets, each corresponding to an n-bit bitmask. Iterate from 0 to 2^n-1; for each mask, include element i if bit i is set.

Time
O(2^n * n)
Space
O(1)
function subsets(nums) {
  const n = nums.length;
  const result = [];
  for (let mask = 0; mask < (1 << n); mask++) {
    const subset = [];
    for (let i = 0; i < n; i++) {
      if (mask & (1 << i)) subset.push(nums[i]);
    }
    result.push(subset);
  }
  return result;
}

Tradeoff:

Airbnb-specific tips

Airbnb uses subsets in the context of amenity filtering: 'Given a host's feature list, generate all valid filter combinations.' Both approaches are accepted, but interviewers expect you to note the 2^n output size and confirm it is acceptable for small n (amenity counts rarely exceed 20). If asked for Subsets II (with duplicates), mention sorting first and skipping duplicate siblings in the DFS loop.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

Drill Subsets and other Airbnb interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →