Distinct permutations by backtracking: Examples & Code

Algorithm Visualizations November 16, 2026 javascript

Published by Dimitris Kougioumtzis · Updated

Choose unused positions and skip equal unused siblings to emit every distinct value permutation once.

Sort the values, then choose an unused position at each depth. Skip a duplicate value when its equal predecessor is still unused, preventing equal sibling branches from generating duplicate permutations.

Open the 3D visualization

Distinct permutations by backtracking example state preview
Preview of the example's final state. Complete values are available in the worked example and interactive timeline.

When to use Distinct permutations by backtracking

Enumerating every distinct order of a small multiset.

Choosing an alternative

Combinations choose increasing positions without considering order. This view considers all orders while merging branches that differ only by identical values.

Worked example: input and state changes

Example input

2,1,2

These checkpoints follow the actual example timeline. State details show the stored values and decisions; use the visualization to inspect every intervening step.

  1. Step 0: Input 1,2,2. Build a choice path; completed rows appear below it.

    State at this checkpoint
    {
      "values": [
        "�",
        "�",
        "�"
      ],
      "active": [],
      "kind": "matrix",
      "columns": 3,
      "result": 0,
      "output": []
    }
  2. Step 5: Undo the choice and explore another branch.

    State at this checkpoint
    {
      "values": [
        1,
        2,
        "�",
        1,
        2,
        2
      ],
      "active": [],
      "kind": "matrix",
      "columns": 3,
      "result": 1,
      "output": [
        1,
        2,
        2
      ]
    }
  3. Step 10: Choose input index 2.

    State at this checkpoint
    {
      "values": [
        2,
        1,
        2,
        1,
        2,
        2
      ],
      "active": [],
      "kind": "matrix",
      "columns": 3,
      "result": 1,
      "output": [
        1,
        2,
        2
      ]
    }
  4. Step 15: Choose input index 0.

    State at this checkpoint
    {
      "values": [
        2,
        2,
        1,
        1,
        2,
        2,
        2,
        1,
        2
      ],
      "active": [],
      "kind": "matrix",
      "columns": 3,
      "result": 2,
      "output": [
        1,
        2,
        2,
        2,
        1,
        2
      ]
    }
  5. Step 20: Generated 3 distinct permutations.

    State at this checkpoint
    {
      "values": [
        "�",
        "�",
        "�",
        1,
        2,
        2,
        2,
        1,
        2,
        2,
        2,
        1
      ],
      "active": [],
      "kind": "matrix",
      "columns": 3,
      "result": 3,
      "output": [
        1,
        2,
        2,
        2,
        1,
        2,
        2,
        2,
        1
      ]
    }

Expected final state

Generated 3 distinct permutations.

Complexity and input bounds

Family: Combinatorics. Time complexity: O(n n!) output-sensitive.

Implementation detail: At most four values bound the output to 24 rows and 96 cells. Downloads sort the input array in place, return the row count and write n values per row in lexicographic value order. Portable versions use an explicit traversal stack; the Python reference recurses.

Space complexity: O(n) traversal state excluding output; Python stores result rows before flattening. Recorded frames add space.

Working-space bounds describe algorithm state and any explicitly noted output, excluding the visualization's saved timeline. Recording frames can use more memory than running the function alone. Here n is sequence length, V and E are vertex and edge counts, and other parameters refer to the named input dimensions.

1..4 values 0..99. Inputs are sorted first; duplicate values do not duplicate results.

The playground validates these limits before starting. Downloaded functions are callable implementations, with parameter and output-buffer contracts in their comments; they do not all repeat the playground's input validation.

Common mistakes and limitations

Restore used markers on backtracking. Sorting alone does not remove duplicate outputs; the unused-predecessor rule is required. The empty input has one empty permutation.

Further reading

For background on algorithm analysis and the JavaScript function interface:

Editorial and testing approach · Browse all algorithm guides

Complete JavaScript implementation

javascript
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
// n 0..4 integer values 0..99. Sorts a in place and emits distinct value permutations in lexicographic order, skipping duplicate unused siblings. Returns row count; output is row-major with n values per row, capacity at least n*n! (at most 96). Empty input has one empty permutation and writes nothing. Explicit stack in portable versions, recursive Python; O(n*n!) worst-case time, O(n) traversal scratch excluding output. Reference snippets assume validated playground inputs. Fixed scratch buffers have 256 slots. Sorting variants may use a different traversal strategy than the animation.
function algorithm(a, n, output) {
    let key = 0; let j = 0;
    for (let i = 1; i < n; i++) { key = a[i]; j = i-1; while (j >= 0 && a[j] > key) { a[j+1] = a[j]; j--; } a[j+1] = key; }
    if (n == 0) { return 1; }
    let chosen = Array(256).fill(0); let next = Array(256).fill(0); let used = Array(256).fill(0); let depth = 0; let count = 0; let candidate = 0;
    while (depth >= 0) { if (depth == n) { for (let k = 0; k < n; k++) { output[count*n+k] = a[chosen[k]]; } count++; depth--; used[chosen[depth]] = 0; }
     else { candidate = next[depth]; while (candidate < n && (used[candidate] != 0 || (candidate > 0 && a[candidate] == a[candidate-1] && used[candidate-1] == 0))) { candidate++; }
     if (candidate == n) { next[depth] = 0; depth--; if (depth >= 0) { used[chosen[depth]] = 0; } }
     else { next[depth] = candidate+1; chosen[depth] = candidate; used[candidate] = 1; depth++; next[depth] = 0; }
     } }
    return count;
}

Source

Author reference for combinatorial generation, not a claim to an original research paper. The playground specifies its own bounded enumeration order and duplicate/position semantics.