Permutations medium

Problem Statement

Given an array of distinct integers nums, 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]]

Steps

The core idea is to use backtracking. We'll explore all possible arrangements recursively. Here's a breakdown of the steps:

1. Base Case: If the current permutation's length equals the length of the input array, add it to the results and return.

2. Recursive Step: For each element in the input array that hasn't been used in the current permutation:

   • Add the element to the current permutation.
   • Recursively call the function with the updated permutation and the remaining unused elements.
   • Remove the element from the current permutation (backtracking). This is crucial to explore other possibilities.

Explanation

Backtracking is a powerful technique for exploring all possible combinations. Imagine a decision tree where each level represents a choice of which element to add to the permutation next. The backtracking step allows us to explore different branches of this tree systematically without getting stuck in a single path. We build the permutations one element at a time, trying each unused element at each step and undoing the choice (backtracking) after exploring all possibilities with that element.

Code

function permute(nums: number[]): number[][] {
    const result: number[][] = [];
    const currentPermutation: number[] = [];
    const used: boolean[] = new Array(nums.length).fill(false); // Track used elements

    function backtrack() {
        if (currentPermutation.length === nums.length) {
            result.push([...currentPermutation]); // Add a copy to avoid modification
            return;
        }

        for (let i = 0; i < nums.length; i++) {
            if (!used[i]) {
                used[i] = true;
                currentPermutation.push(nums[i]);
                backtrack();
                currentPermutation.pop(); // Backtrack: remove the last element
                used[i] = false;
            }
        }
    }

    backtrack();
    return result;
}


//Example usage
console.log(permute([1,2,3])); // Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
console.log(permute([0,1])); // Output: [[0,1],[1,0]]

Complexity

• Time Complexity: O(n * n!), where n is the length of the input array. This is because there are n! permutations, and for each permutation, we perform O(n) operations to add/remove elements.

• Space Complexity: O(n), primarily due to the recursive call stack and the currentPermutation array. The used array also contributes O(n) space. The result array's space complexity is O(n * n!) but it's not considered in the recursive space complexity analysis because it only holds the final results after all the recursion is done.