SimuVedaAlgorithms Lab Open in the lab

Backtracking / Intermediate

Permutations Visualizer

Fill the answer one position at a time. At each position try every value not used yet, go deeper, then give the value back so the next branch can use it.

Start the Permutations simulation → Step forward and back, change the input, follow the code line by line in Java, Python, C++, C or JavaScript. Free, no sign-up.

Time and space complexity

Best timeO(n·n!)
Average timeO(n·n!)
Worst timeO(n·n!)
Extra spaceO(n)

Worked example, step by step

The same steps the simulator shows, on a small input.

  1. Put 1 at position 0.
  2. 1 is already in the path. Skip it.
  3. Put 2 at position 1.
  4. 1 is already in the path. Skip it.
  5. 2 is already in the path. Skip it.
  6. Put 3 at position 2.
  7. Every value is placed. Save [1, 2, 3].
  8. Undo: take 3 back out and try the next value here.
  9. Undo: take 2 back out and try the next value here.
  10. Put 3 at position 1.
  11. 1 is already in the path. Skip it.
  12. Put 2 at position 2.
  13. Every value is placed. Save [1, 3, 2].
  14. Undo: take 2 back out and try the next value here.
  15. 3 is already in the path. Skip it.
  16. Undo: take 3 back out and try the next value here.
  17. Undo: take 1 back out and try the next value here.
  18. Put 2 at position 0.
  19. Put 1 at position 1.
  20. 1 is already in the path. Skip it.
  21. … 28 more steps …
  22. Undo: take 2 back out and try the next value here.
  23. 3 is already in the path. Skip it.
  24. Undo: take 3 back out and try the next value here.
  25. Done. 6 permutations, which is 3!.

Try it with your own input →

Backtracking: permutations in Java, Python, C++, C and JavaScript

void backtrack(List<Integer> path, boolean[] used) {
  if (path.size() == nums.length) {
    result.add(new ArrayList<>(path));
    return;
  }
  for (int i = 0; i < nums.length; i++) {
    if (used[i]) continue;
    used[i] = true; path.add(nums[i]);
    backtrack(path, used);
    used[i] = false; path.remove(path.size() - 1);
  }
}
def backtrack(path, used):
    if len(path) == len(nums):
        result.append(path[:])
        return
    for i in range(len(nums)):
        if used[i]:
            continue
        used[i] = True; path.append(nums[i])
        backtrack(path, used)
        used[i] = False; path.pop()
void backtrack(vector<int>& path, vector<bool>& used) {
  if (path.size() == nums.size()) {
    result.push_back(path);
    return;
  }
  for (int i = 0; i < (int)nums.size(); i++) {
    if (used[i]) continue;
    used[i] = true; path.push_back(nums[i]);
    backtrack(path, used);
    used[i] = false; path.pop_back();
  }
}
int nums[10], n, path[10], plen, used[10];

void backtrack(void) {
  if (plen == n) {
    record(path, plen);   /* save a copy of path */
    return;
  }
  for (int i = 0; i < n; i++) {
    if (used[i]) continue;
    used[i] = 1; path[plen++] = nums[i];
    backtrack();
    used[i] = 0; plen--;
  }
}
function backtrack(path, used) {
  if (path.length === nums.length) {
    result.push([...path]);
    return;
  }
  for (let i = 0; i < nums.length; i++) {
    if (used[i]) continue;
    used[i] = true; path.push(nums[i]);
    backtrack(path, used);
    used[i] = false; path.pop();
  }
}

In an interview

LeetCode 46, Permutations. With duplicates in the input it becomes 47 Permutations II: sort first and skip equal neighbours.

Compare with subsets: subsets decides include or skip per value (2ⁿ leaves); permutations decides which unused value goes next (n! leaves). The used[] array is the only extra state.

More backtracking