78. Subsets

Difficulty: MEDIUM

Problem description can be found here.

Approach

Can follow a typical Backtracking problem template.

Solution

function subsets(nums: number[]): number[][] {
  const result: number[][] = [];

  // path is the current subset we are building
  function backtrack(index: number, path: number[]) {
    // Base case
    if (index === nums.length) {
      result.push(path.slice());
      return;
    }

    // Decision 1: Include nums[index]
    path.push(nums[index]);
    backtrack(index + 1, path);
    // Back tracking portion
    path.pop();

    // Decision 2: Skip nums[index]
    backtrack(index + 1, path);
  }

  backtrack(0, []);

  return result;
}

subsets([1, 2, 3]); // [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]