Permutations

Concept

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

A Permutation is a specific rearrangement of elements. The array [1, 2, 3] has a length of 3. Every valid permutation MUST also have exactly a length of 3, just in a different order.
[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1].

The total number of permutations is mathematically N-Factorial ($N!$).
For an array of length 3, there are $3 \times 2 \times 1 = 6$ permutations.

The Strategy

We use standard Backtracking.
Because every number from the input array must eventually be used in the permutation, our for loop always scans the entire input array from index 0.
However, we cannot use the exact same number twice in a single permutation (no [1, 1, 1]).
To prevent this, we must maintain a used Hash Set (or a boolean array) to physically block the recursion from picking numbers it is already holding in its current path.

Implementation

// Time Complexity: O(N * N!) (N! permutations, and each takes O(N) time to clone into the result array)
// Space Complexity: O(N) (The call stack depth and the currentPath array)

function permute(nums: number[]): number[][] {
    const result: number[][] = [];
    const currentPath: number[] = [];
    
    // We use a Set to get O(1) lookups to check if a number is already in the path
    const used = new Set<number>();

    function backtrack() {
        // 1. BASE CASE: The permutation is full!
        if (currentPath.length === nums.length) {
            result.push([...currentPath]); // Clone and save
            return;
        }

        // 2. EXPLORE: We must try EVERY number in the original array
        for (let i = 0; i < nums.length; i++) {
            const num = nums[i];

            // If we are already using this number in our current path, skip it!
            if (used.has(num)) continue;

            // 3. DO: Make the choice
            currentPath.push(num);
            used.add(num);

            // 4. RECURSE: Dig deeper
            backtrack();

            // 5. UNDO: Backtrack so the loop can try the next number
            currentPath.pop();
            used.delete(num);
        }
    }

    backtrack();
    return result;
}

The Optimal Swap Approach (No Extra Space)

There is a highly advanced way to generate permutations without using the extra used Set or the currentPath array.

Instead of building a new array, you dynamically Swap elements within the original nums array itself.

1. Swap index 0 with index 0, recurse.
2. Backtrack (Swap them back to restore order).
3. Swap index 0 with index 1, recurse.
4. Backtrack… etc.
   When the recursive depth reaches the end of the array, the nums array is currently sitting in a valid permutated state! Clone it and save it.

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

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

        for (let i = startIndex; i < nums.length; i++) {
            // Swap
            [nums[startIndex], nums[i]] = [nums[i], nums[startIndex]];
            
            // Recurse (locking in the startIndex position)
            backtrack(startIndex + 1);
            
            // Backtrack (Swap back!)
            [nums[startIndex], nums[i]] = [nums[i], nums[startIndex]];
        }
    }

    backtrack(0);
    return result;
}

Interview Questions

Q: What happens if the input array contains duplicate numbers? (e.g., [1, 1, 2])
A: This is LeetCode #47 (Permutations II). If you run standard backtracking on it, it will treat the two 1s as completely different entities, generating identical duplicate permutations in the final output ([1, 1, 2] and [1, 1, 2]).
To prevent this, you must Sort the array first. Then, inside the for loop, you add a deduplication check: if (i > 0 && nums[i] === nums[i - 1] && !used[i - 1]) continue;. This guarantees that identical numbers are processed in a strict left-to-right order, perfectly pruning redundant recursive branches.