7.1 Subsets / Permutations / Combinations

Demo: Subsets — LC 78 (Medium — Meta/Amazon High)

Statement (Demo): Given an integer array nums of unique elements, return every possible subset (the power set), with no duplicate subsets. Example: nums=[1,2,3] → [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]] | ⚡ nums.length ≤ 10

Approach: At each level, take the elements from start onward one by one — every state of the path is a subset. Recurse after taking, pop (undo) on the way back — that push/pop pair is backtracking.

function subsets(nums) {
  const res = [];
  const backtrack = (start, path) => {
    res.push([...path]); // every state is an answer
    for (let i = start; i < nums.length; i++) {
      path.push(nums[i]); // choose
      backtrack(i + 1, path); // explore
      path.pop(); // undo
    }
  };
  backtrack(0, []);
  return res;
}

Complexity: Time O(n · 2ⁿ), Space O(n) for the path