#46
Permutations
Medium Backtracking with used[]
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Return all orderings of an array of distinct integers.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: every ordering of distinct numbers.
Why this works: fill positions one by one with any unused number; undo after exploring.
Example: [1, 2, 3]
1 → 2 → 3, 1 → 3 → 22 → 1 → 3, 2 → 3 → 13 → 1 → 2, 3 → 2 → 1
✦Hints open one at a time
Build the permutation one position at a time.
Track which elements are already used.
↗Approach
At each level try every unused element, mark it used, recurse, then unmark. When the path has n elements, record a copy.
</>Solution (Java)
import java.util.*;
class Solution {
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
backtrack(nums, new boolean[nums.length], new ArrayList<>(), res);
return res;
}
private void backtrack(int[] nums, boolean[] used, List<Integer> path, List<List<Integer>> res) {
if (path.size() == nums.length) {
res.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(nums, used, path, res);
path.remove(path.size() - 1);
used[i] = false; // undo
}
}
}!Common mistake
Forgetting to unmark used[i] after the recursive call.
Complexity
- Time: O(n · n!).
- Space: O(n).
Topic: Recursion & Backtracking
🎬 Episodes 29–36: video coming soon