046. Permutations

At a Glance

• Topic: Array
• Pattern: Analyze Pattern
• Difficulty: Medium
• LeetCode: 046

Problem Statement

Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order.

Example 1: Input: nums = [1,2,3] Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]] Example 2: Input: nums = [0,1] Output: [[0,1],[1,0]] Example 3: Input: nums = [1] Output: [[1]]

Constraints:

1 <= nums.length <= 6
-10 <= nums[i] <= 10
All the integers of nums are unique.

Approach & Solution Steps

• Next permutation repeated — possible but indirect.
• Optimal — DFS pick unused elements — O(n * n!) time for output size.

Optimal JS Solution

function permute(nums) {
  const result = [];
  const path = [];
  const visited = new Array(nums.length).fill(false);

  function dfs() {
    if (path.length === nums.length) {
      result.push([...path]);
      return;
    }
    for (let index = 0; index < nums.length; index += 1) {
      if (visited[index]) {
        continue;
      }
      visited[index] = true;
      path.push(nums[index]);
      dfs();
      path.pop();
      visited[index] = false;
    }
  }

  dfs();
  return result;
}

Edge Cases & Pitfalls

• Always consider empty or null inputs.
• Watch out for off-by-one index errors.