How do you generate all permutations of an array using backtracking?
Build the permutation one position at a time. Try every unused element at the current position, mark it used, recurse, then unmark it. A complete path of length n is one permutation; there are n! of them.
Explain it simply
Imagine arranging three friends in a photo. For the first spot you have three choices, for the second two, for the last one. That is 3 x 2 x 1 = 6 arrangements.
A used array remembers who is already in the photo. After finishing one arrangement you step back, remove the last person and try someone else in that spot.
Example
function permutations(nums) {
const result = [];
const path = [];
const used = new Array(nums.length).fill(false);
function backtrack() {
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.pop();
used[i] = false;
}
}
backtrack();
return result;
}
console.log(JSON.stringify(permutations([1, 2, 3])));
// Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]Complexity
Time O(n * n!), space O(n) beyond the output.
What to say in the interview
"At each depth I try every element not yet used, add it to the path, recurse, then undo the choice. When the path has n elements I save a copy. There are n! results, so time is O(n * n!) and the recursion uses O(n) extra space. For duplicates I would sort and skip equal siblings."
Common mistakes
- Forgetting to reset used[i] after recursion.
- Saving the path reference instead of a copy.