[Algorithm] Backtracking - permutations(Phase by Phase) leetcode-46

Backtracking - permutations

Analisis recursive

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]]

Solution

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

  function backtrack() {
    // Base case: If partialPermutation is complete, push a copy of it
    if (subArr.length === nums.length) {
      // Caution! : permutations.push(partialPermutation); // Create a copy of the current permutation
      result.push([...subArr]); // Create a copy of the current permutation
      return;
    }

    for (const num of nums) {
      if (!subArr.includes(num)) {
        subArr.push(num);
        backtrack(); // Recurse
        subArr.pop(); // Backtrack
      }
    }
  }

  backtrack(); // Start the backtracking process
  return result;
}