Permutations in javascript

💡 General Theory

          n !
nPr = ----------
       (n - r) !

🔥 Permutations

const permutations = (array, length = array.length) => {
  const res = [];

  const dfs = (cur, remain) => {
    if (cur.length === length) {
      res.push([...cur]);
      return;
    }

    for (let i = 0; i < remain.length; i += 1) {
      cur.push(remain[i]);
      dfs(cur, [...remain.slice(0, i), ...remain.slice(i + 1)]);
      cur.pop();
    }
  };

  dfs([], array);

  return res;
};

const nums = [1, 2, 3, 4, 5];
const result = permutations(nums, 2);

/*
0: (2) [1, 2]
1: (2) [1, 3]
2: (2) [1, 4]
3: (2) [1, 5]
4: (2) [2, 1]
5: (2) [2, 3]
6: (2) [2, 4]
7: (2) [2, 5]
8: (2) [3, 1]
9: (2) [3, 2]
10: (2) [3, 4]
11: (2) [3, 5]
12: (2) [4, 1]
13: (2) [4, 2]
14: (2) [4, 3]
15: (2) [4, 5]
16: (2) [5, 1]
17: (2) [5, 2]
18: (2) [5, 3]
19: (2) [5, 4]
*/

Generate fixed length permutations

• Exchange one element nums[first] with the others nums[first:]
• without array slicing

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var permute = function (nums) {
  const N = nums.length;

  const res = [];

  const backtrack = (first) => {
    if (first >= N) {
      res.push([...nums]);
      return;
    }

    for (let i = first; i < N; i += 1) {
      [nums[first], nums[i]] = [nums[i], nums[first]];
      backtrack(first + 1)[(nums[first], nums[i])] = [nums[i], nums[first]];
    }
  };

  backtrack(0);

  return res;
};

🗒️ Typical problems

• 46. Permutations - Leetcode