46. Permutations

Difficulty: MEDIUM

Problem description can be found here.

Approach

Can follow a typical Backtracking problem template. Noting the correct constraint.

Solution

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

  function backtrack(path: number[]) {
    if (path.length === nums.length) {
      result.push(path.slice());
      return;
    }

    for (const num of nums) {
      if (path.includes(num)) {
        continue;
      }

      path.push(num);
      backtrack(path);
      path.pop();
    }
  }

  backtrack([]);

  return result;
}

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