Skip to main content

62. Subsets

mediumAsked at Ola

Return all subsets of a distinct integer array.

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.

Constraints

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

Examples

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

Approaches

1. Iterative grow

Start with [[]] and for each number append a copy with that number added.

Time
O(2^n * n)
Space
O(2^n)
let out = [[]];
for (const x of nums) out = [...out, ...out.map(s => [...s, x])];
return out;

Tradeoff:

2. DFS include/exclude

Recurse at each index; either include nums[i] or not.

Time
O(2^n * n)
Space
O(n)
function subsets(nums) {
  const out = [];
  const dfs = (i, path) => {
    if (i === nums.length) { out.push([...path]); return; }
    dfs(i+1, path);
    path.push(nums[i]);
    dfs(i+1, path);
    path.pop();
  };
  dfs(0, []);
  return out;
}

Tradeoff:

Ola-specific tips

Ola interviewers prefer the include/exclude DFS shape for transferable recursion; tie it to picking subsets of zones to A/B test new dispatch policies.

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 Ola interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →