Demo preview: These solutions pass the automated test suite but have not been human-reviewed. Treat trade-offs and prose as draft.

Mediumbacktracking

Subsets

Problem (restated)

Return all subsets of a distinct integer array (power set).

Intuition

At each index: skip or take, then recurse. Record path at every node.

Approaches

Include/exclude DFS

Tested only

Time O(n * 2^n)Space O(n)

Idea. dfs(i): append path; for j>=i take nums[j], dfs(j+1), undo.

Walkthrough. [1,2,3] → 8 subsets including [] and full set.

Trade-offs. Bit mask iteration is O(n·2^n) too; backtracking is the template.

Solution

export function subsets(nums: number[]): number[][] {
  const res: number[][] = [];
  const path: number[] = [];
  const dfs = (start: number) => {
    res.push([...path]);
    for (let i = start; i < nums.length; i++) {
      path.push(nums[i]!);
      dfs(i + 1);
      path.pop();
    }
  };
  dfs(0);
  return res;
}

export function subsets(nums: number[]): number[][] {
  const res: number[][] = [];
  const path: number[] = [];
  const dfs = (start: number) => {
    res.push([...path]);
    for (let i = start; i < nums.length; i++) {
      path.push(nums[i]!);
      dfs(i + 1);
      path.pop();
    }
  };
  dfs(0);
  return res;
}

Template connection

Backtracking choose/explore/undo.

Reflection

Which pattern gave this away within 90 seconds?
What changed from the standard template?
What would break the current solution?