29. Permutations
Given an array nums of distinct integers, return all the possible permutations in any order.
How It Works & Algorithmic Design
Solves using Backtracking with Visited State Tracking:
- Visited Tracking: Maintain a boolean array or set
visitedto avoid reusing the same element in a single permutation. - Backtrack Loop:
- If
currentPath.length === nums.length, save copy ofcurrentPathintoresand return. - Loop $i$ from $0$ to
nums.length - 1:- If
visited[i]is true, continue. - Set
visited[i] = true, pushnums[i]intocurrentPath. - Recurse:
backtrack(). - Undo:
visited[i] = false,currentPath.pop().
- If
- If
Why This Approach Works Best
Generates all $n!$ unique orderings systematically in $O(n \cdot n!)$ time.
Example Walkthrough
Input:
[1, 2, 3]3 distinct numbers.
Permutation Count:
3! = 6 permutations[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]].
Answer: Permutation generation using Backtracking
function permute(nums) {
const res = [], visited = new Array(nums.length).fill(false);
function backtrack(path) {
if (path.length === nums.length) {
res.push([...path]);
return;
}
for (let i = 0; i < nums.length; i++) {
if (visited[i]) continue;
visited[i] = true;
path.push(nums[i]);
backtrack(path);
path.pop();
visited[i] = false;
}
}
backtrack([]);
return res;
}💡 Explore all $n!$ element arrangements using recursive backtracking and visited state tracking.
Key Takeaways
- Tracks visited indices to prevent reusing elements in the same permutation.
- Total number of generated permutations is $n!$.
- Time complexity $O(n \cdot n!)$.