Permutations via Backtracking

Backtracking generates all permutations by swapping elements into each position recursively, then undoing the swap to explore the next branch.

5 min read Level 3/5 #dsa#recursion#backtracking

What you'll learn

Implement permutation generation using the swap-based backtracking method
Analyze why the time complexity is O(n·n!) and space complexity is O(n)
Prune duplicate permutations by sorting and skipping repeated swap targets

A permutation is an ordered arrangement of all elements in a set. For n distinct elements there are n! permutations. Backtracking generates them by fixing one element at each position and recursing on the remaining positions, then undoing the choice (backtracking) before trying the next element.

Swap-Based Algorithm

The swap approach avoids allocating extra arrays for each sub-problem — it rearranges elements in place and swaps back when done:

function permutations(arr) {
  const result = [];

  function backtrack(start) {
    // Base case: all positions are fixed
    if (start === arr.length) {
      result.push([...arr]); // snapshot the current arrangement
      return;
    }

    for (let i = start; i < arr.length; i++) {
      // Choose: swap element i into position `start`
      [arr[start], arr[i]] = [arr[i], arr[start]];

      // Explore: fix the next position
      backtrack(start + 1);

      // Undo: restore the array for the next iteration
      [arr[start], arr[i]] = [arr[i], arr[start]];
    }
  }

  backtrack(0);
  return result;
}

console.log(permutations([1, 2, 3]));
// [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,2,1],[3,1,2]]

At each depth d, the loop tries n - d choices. The total number of leaf nodes (complete permutations) is n!, and each leaf requires O(n) work to copy the array — giving O(n · n!) total time. The recursion depth is n, so the call stack uses O(n) space (not counting the output).

Complexity

n	n!	O(n·n!) operations
5	120	600
8	40 320	322 560
10	3 628 800	36 288 000
12	479 001 600	~5.7 billion

Permutation generation is inherently expensive — n=12 is typically the practical limit for in-memory results.

Pruning Duplicates

When the input contains repeated values, the above code generates duplicate permutations. Sort the array first and skip swapping with an element that is identical to one already tried at the same position:

function permutationsUnique(arr) {
  arr.sort((a, b) => a - b);
  const result = [];

  function backtrack(start) {
    if (start === arr.length) {
      result.push([...arr]);
      return;
    }

    const seen = new Set();
    for (let i = start; i < arr.length; i++) {
      if (seen.has(arr[i])) continue; // skip duplicate choice at this position
      seen.add(arr[i]);

      [arr[start], arr[i]] = [arr[i], arr[start]];
      backtrack(start + 1);
      [arr[start], arr[i]] = [arr[i], arr[start]];
    }
  }

  backtrack(0);
  return result;
}

console.log(permutationsUnique([1, 1, 2]).length); // 3 (not 6)

Up Next

Combinations are like permutations but order does not matter — backtracking with a start index prunes the search space to just the relevant branches.

Combinations via Backtracking →