subsets.ts

/**
 * 78. Subsets  (Medium)
 * Link: https://leetcode.com/problems/subsets/
 *
 * Given an array of unique integers, return all possible subsets (the power
 * set). The solution must not contain duplicate subsets.
 *
 * Example:
 *   Input:  nums = [1, 2, 3]
 *   Output: [[], [1], [2], [3], [1,2], [1,3], [2,3], [1,2,3]]
 *
 * Approach:
 *   Backtracking. Walk the array from a start index; at each step choose to
 *   include nums[i], recurse on the remainder, then backtrack (remove it). The
 *   `start` index prevents revisiting earlier elements, so each subset is
 *   generated exactly once.
 *
 * Time:  O(n * 2^n)  — 2^n subsets, each up to length n to copy.
 * Space: O(n)        — recursion depth / current path (excluding output).
 */
export function subsets(nums: number[]): number[][] {
  const result: number[][] = [];
  const path: number[] = [];

  function backtrack(start: number): void {
    result.push([...path]);
    for (let i = start; i < nums.length; i++) {
      path.push(nums[i]);
      backtrack(i + 1);
      path.pop();
    }
  }

  backtrack(0);
  return result;
}