Permutations
MediumChoose an unused element at each level
Place each unused item in the next spot and recurse, building every ordering.
The idea
Each level of the tree picks one element that hasn't been used yet. When the path length equals n, it's a complete permutation.
1
2
3
0
1
2
Step 1 of 8. Pick an unused element at each level → 3! = 6 permutations. Values: 1, 2, 3.
1/8
Optimal
timeO(n·n!)spaceO(n)
Track which are placed.
1function dfs(path, used) {2 if (path.length === n) { out.push([...path]); return; }3 for (let i = 0; i < n; i++) {4 if (used[i]) continue;5 used[i] = true; path.push(nums[i]);6 dfs(path, used);7 path.pop(); used[i] = false;8 }9}Input
- array
- [1, 2, 3]
Memory
- perm
- —
Output
- count
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- nums = [1, 2, 3]
- Output:
- [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
- Explanation:
- All 6 orderings of three items.
Example 2
- Input:
- nums = [0, 1]
- Output:
- [[0, 1], [1, 0]]
- Explanation:
- [0,1] and [1,0].
Example 3
- Input:
- nums = [1]
- Output:
- [[1]]
- Explanation:
- One arrangement.
Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.