13.2 Permutations problem¶
Generating permutations is a classic application of backtracking. Given a collection, such as an array or a string, the task is to find every possible ordering of its elements.
Table 13-2 gives several input arrays and all their permutations.
Table 13-2 Examples of permutations
| Input array | All permutations |
|---|---|
| \([1]\) | \([1]\) |
| \([1, 2]\) | \([1, 2], [2, 1]\) |
| \([1, 2, 3]\) | \([1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]\) |
13.2.1 Distinct elements¶
Question
Given an integer array with no duplicate elements, return all possible permutations.
From a backtracking perspective, we can view a permutation as the result of a sequence of choices. For input \([1, 2, 3]\), choosing \(1\), then \(3\), then \(2\) produces \([1, 3, 2]\). Backtracking undoes a choice so that other choices can be tried.
In the code, choices contains all the input elements, and state contains the elements chosen so far. Each element may be chosen only once, so every element in state must be unique.
As shown in Figure 13-5, we can expand the search into a recursion tree, where each node represents the current state. Starting from the root, three rounds of choices lead to a leaf, and each leaf corresponds to one permutation.
Figure 13-5 Recursion tree for permutations
1. Pruning repeated selections¶
To ensure that each element is chosen only once, introduce a Boolean array selected, where selected[i] indicates whether choices[i] has been chosen. Use it for the following pruning steps.
- After choosing
choices[i], setselected[i]to \(\text{True}\) to mark it as selected. - When iterating over
choices, skip all selected elements, pruning their branches.
As shown in Figure 13-6, if we choose 1 first, 3 second, and 2 third, we must prune the branch for 1 in the second round and the branches for 1 and 3 in the third round.
Figure 13-6 Example of pruning permutations
This pruning reduces the search space from \(O(n^n)\) to \(O(n!)\).
2. Code implementation¶
With these details established, we can fill in the backtracking template. To keep the code short, we inline the template's helper functions into backtrack():
permutations_i.py
def backtrack(
state: list[int], choices: list[int], selected: list[bool], res: list[list[int]]
):
"""Backtracking: permutations I"""
# Record a solution when the state length equals the number of elements
if len(state) == len(choices):
res.append(list(state))
return
# Iterate over all choices
for i, choice in enumerate(choices):
# Prune: do not choose an element more than once
if not selected[i]:
# Try: make a choice and update the state
selected[i] = True
state.append(choice)
# Proceed to the next choice
backtrack(state, choices, selected, res)
# Backtrack: undo the choice and restore the previous state
selected[i] = False
state.pop()
def permutations_i(nums: list[int]) -> list[list[int]]:
"""Permutations I"""
res = []
backtrack(state=[], choices=nums, selected=[False] * len(nums), res=res)
return res
permutations_i.cpp
/* Backtracking: permutations I */
void backtrack(vector<int> &state, const vector<int> &choices, vector<bool> &selected, vector<vector<int>> &res) {
// Record a solution when the state length equals the number of elements
if (state.size() == choices.size()) {
res.push_back(state);
return;
}
// Iterate over all choices
for (int i = 0; i < choices.size(); i++) {
int choice = choices[i];
// Prune: do not choose an element more than once
if (!selected[i]) {
// Try: make a choice and update the state
selected[i] = true;
state.push_back(choice);
// Proceed to the next choice
backtrack(state, choices, selected, res);
// Backtrack: undo the choice and restore the previous state
selected[i] = false;
state.pop_back();
}
}
}
/* Permutations I */
vector<vector<int>> permutationsI(vector<int> nums) {
vector<int> state;
vector<bool> selected(nums.size(), false);
vector<vector<int>> res;
backtrack(state, nums, selected, res);
return res;
}
permutations_i.java
/* Backtracking: permutations I */
void backtrack(List<Integer> state, int[] choices, boolean[] selected, List<List<Integer>> res) {
// Record a solution when the state length equals the number of elements
if (state.size() == choices.length) {
res.add(new ArrayList<Integer>(state));
return;
}
// Iterate over all choices
for (int i = 0; i < choices.length; i++) {
int choice = choices[i];
// Prune: do not choose an element more than once
if (!selected[i]) {
// Try: make a choice and update the state
selected[i] = true;
state.add(choice);
// Proceed to the next choice
backtrack(state, choices, selected, res);
// Backtrack: undo the choice and restore the previous state
selected[i] = false;
state.remove(state.size() - 1);
}
}
}
/* Permutations I */
List<List<Integer>> permutationsI(int[] nums) {
List<List<Integer>> res = new ArrayList<List<Integer>>();
backtrack(new ArrayList<Integer>(), nums, new boolean[nums.length], res);
return res;
}
permutations_i.cs
/* Backtracking: permutations I */
void Backtrack(List<int> state, int[] choices, bool[] selected, List<List<int>> res) {
// Record a solution when the state length equals the number of elements
if (state.Count == choices.Length) {
res.Add(new List<int>(state));
return;
}
// Iterate over all choices
for (int i = 0; i < choices.Length; i++) {
int choice = choices[i];
// Prune: do not choose an element more than once
if (!selected[i]) {
// Try: make a choice and update the state
selected[i] = true;
state.Add(choice);
// Proceed to the next choice
Backtrack(state, choices, selected, res);
// Backtrack: undo the choice and restore the previous state
selected[i] = false;
state.RemoveAt(state.Count - 1);
}
}
}
/* Permutations I */
List<List<int>> PermutationsI(int[] nums) {
List<List<int>> res = [];
Backtrack([], nums, new bool[nums.Length], res);
return res;
}
permutations_i.go
/* Backtracking: permutations I */
func backtrackI(state *[]int, choices *[]int, selected *[]bool, res *[][]int) {
// Record a solution when the state length equals the number of elements
if len(*state) == len(*choices) {
newState := append([]int{}, *state...)
*res = append(*res, newState)
}
// Iterate over all choices
for i := 0; i < len(*choices); i++ {
choice := (*choices)[i]
// Prune: do not choose an element more than once
if !(*selected)[i] {
// Try: make a choice and update the state
(*selected)[i] = true
*state = append(*state, choice)
// Proceed to the next choice
backtrackI(state, choices, selected, res)
// Backtrack: undo the choice and restore the previous state
(*selected)[i] = false
*state = (*state)[:len(*state)-1]
}
}
}
/* Permutations I */
func permutationsI(nums []int) [][]int {
res := make([][]int, 0)
state := make([]int, 0)
selected := make([]bool, len(nums))
backtrackI(&state, &nums, &selected, &res)
return res
}
permutations_i.swift
/* Backtracking: permutations I */
func backtrack(state: inout [Int], choices: [Int], selected: inout [Bool], res: inout [[Int]]) {
// Record a solution when the state length equals the number of elements
if state.count == choices.count {
res.append(state)
return
}
// Iterate over all choices
for (i, choice) in choices.enumerated() {
// Prune: do not choose an element more than once
if !selected[i] {
// Try: make a choice and update the state
selected[i] = true
state.append(choice)
// Proceed to the next choice
backtrack(state: &state, choices: choices, selected: &selected, res: &res)
// Backtrack: undo the choice and restore the previous state
selected[i] = false
state.removeLast()
}
}
}
/* Permutations I */
func permutationsI(nums: [Int]) -> [[Int]] {
var state: [Int] = []
var selected = Array(repeating: false, count: nums.count)
var res: [[Int]] = []
backtrack(state: &state, choices: nums, selected: &selected, res: &res)
return res
}
permutations_i.js
/* Backtracking: permutations I */
function backtrack(state, choices, selected, res) {
// Record a solution when the state length equals the number of elements
if (state.length === choices.length) {
res.push([...state]);
return;
}
// Iterate over all choices
choices.forEach((choice, i) => {
// Prune: do not choose an element more than once
if (!selected[i]) {
// Try: make a choice and update the state
selected[i] = true;
state.push(choice);
// Proceed to the next choice
backtrack(state, choices, selected, res);
// Backtrack: undo the choice and restore the previous state
selected[i] = false;
state.pop();
}
});
}
/* Permutations I */
function permutationsI(nums) {
const res = [];
backtrack([], nums, Array(nums.length).fill(false), res);
return res;
}
permutations_i.ts
/* Backtracking: permutations I */
function backtrack(
state: number[],
choices: number[],
selected: boolean[],
res: number[][]
): void {
// Record a solution when the state length equals the number of elements
if (state.length === choices.length) {
res.push([...state]);
return;
}
// Iterate over all choices
choices.forEach((choice, i) => {
// Prune: do not choose an element more than once
if (!selected[i]) {
// Try: make a choice and update the state
selected[i] = true;
state.push(choice);
// Proceed to the next choice
backtrack(state, choices, selected, res);
// Backtrack: undo the choice and restore the previous state
selected[i] = false;
state.pop();
}
});
}
/* Permutations I */
function permutationsI(nums: number[]): number[][] {
const res: number[][] = [];
backtrack([], nums, Array(nums.length).fill(false), res);
return res;
}
permutations_i.dart
/* Backtracking: permutations I */
void backtrack(
List<int> state,
List<int> choices,
List<bool> selected,
List<List<int>> res,
) {
// Record a solution when the state length equals the number of elements
if (state.length == choices.length) {
res.add(List.from(state));
return;
}
// Iterate over all choices
for (int i = 0; i < choices.length; i++) {
int choice = choices[i];
// Prune: do not choose an element more than once
if (!selected[i]) {
// Try: make a choice and update the state
selected[i] = true;
state.add(choice);
// Proceed to the next choice
backtrack(state, choices, selected, res);
// Backtrack: undo the choice and restore the previous state
selected[i] = false;
state.removeLast();
}
}
}
/* Permutations I */
List<List<int>> permutationsI(List<int> nums) {
List<List<int>> res = [];
backtrack([], nums, List.filled(nums.length, false), res);
return res;
}
permutations_i.rs
/* Backtracking: permutations I */
fn backtrack(mut state: Vec<i32>, choices: &[i32], selected: &mut [bool], res: &mut Vec<Vec<i32>>) {
// Record a solution when the state length equals the number of elements
if state.len() == choices.len() {
res.push(state);
return;
}
// Iterate over all choices
for i in 0..choices.len() {
let choice = choices[i];
// Prune: do not choose an element more than once
if !selected[i] {
// Try: make a choice and update the state
selected[i] = true;
state.push(choice);
// Proceed to the next choice
backtrack(state.clone(), choices, selected, res);
// Backtrack: undo the choice and restore the previous state
selected[i] = false;
state.pop();
}
}
}
/* Permutations I */
fn permutations_i(nums: &mut [i32]) -> Vec<Vec<i32>> {
let mut res = Vec::new(); // Result list (permutations)
backtrack(Vec::new(), nums, &mut vec![false; nums.len()], &mut res);
res
}
permutations_i.c
/* Backtracking: permutations I */
void backtrack(int *state, int stateSize, int *choices, int choicesSize, bool *selected, int **res, int *resSize) {
// Record a solution when the state length equals the number of elements
if (stateSize == choicesSize) {
res[*resSize] = (int *)malloc(choicesSize * sizeof(int));
for (int i = 0; i < choicesSize; i++) {
res[*resSize][i] = state[i];
}
(*resSize)++;
return;
}
// Iterate over all choices
for (int i = 0; i < choicesSize; i++) {
int choice = choices[i];
// Prune: do not choose an element more than once
if (!selected[i]) {
// Try: make a choice and update the state
selected[i] = true;
state[stateSize] = choice;
// Proceed to the next choice
backtrack(state, stateSize + 1, choices, choicesSize, selected, res, resSize);
// Backtrack: undo the choice and restore the previous state
selected[i] = false;
}
}
}
/* Permutations I */
int **permutationsI(int *nums, int numsSize, int *returnSize) {
int *state = (int *)malloc(numsSize * sizeof(int));
bool *selected = (bool *)malloc(numsSize * sizeof(bool));
for (int i = 0; i < numsSize; i++) {
selected[i] = false;
}
int **res = (int **)malloc(MAX_SIZE * sizeof(int *));
*returnSize = 0;
backtrack(state, 0, nums, numsSize, selected, res, returnSize);
free(state);
free(selected);
return res;
}
permutations_i.kt
/* Backtracking: permutations I */
fun backtrack(
state: MutableList<Int>,
choices: IntArray,
selected: BooleanArray,
res: MutableList<MutableList<Int>?>
) {
// Record a solution when the state length equals the number of elements
if (state.size == choices.size) {
res.add(state.toMutableList())
return
}
// Iterate over all choices
for (i in choices.indices) {
val choice = choices[i]
// Prune: do not choose an element more than once
if (!selected[i]) {
// Try: make a choice and update the state
selected[i] = true
state.add(choice)
// Proceed to the next choice
backtrack(state, choices, selected, res)
// Backtrack: undo the choice and restore the previous state
selected[i] = false
state.removeAt(state.size - 1)
}
}
}
/* Permutations I */
fun permutationsI(nums: IntArray): MutableList<MutableList<Int>?> {
val res = mutableListOf<MutableList<Int>?>()
backtrack(mutableListOf(), nums, BooleanArray(nums.size), res)
return res
}
permutations_i.rb
### Backtracking: permutations I ###
def backtrack(state, choices, selected, res)
# Record a solution when the state length equals the number of elements
if state.length == choices.length
res << state.dup
return
end
# Iterate over all choices
choices.each_with_index do |choice, i|
# Prune: do not choose an element more than once
unless selected[i]
# Try: make a choice and update the state
selected[i] = true
state << choice
# Proceed to the next choice
backtrack(state, choices, selected, res)
# Backtrack: undo the choice and restore the previous state
selected[i] = false
state.pop
end
end
end
### Permutations I ###
def permutations_i(nums)
res = []
backtrack([], nums, Array.new(nums.length, false), res)
res
end
Visualize execution
13.2.2 Duplicate elements¶
Question
Given an integer array that may contain duplicate elements, return all distinct permutations.
Suppose the input is \([1, 1, 2]\). To distinguish the two occurrences of \(1\), denote the second \(1\) by \(\hat{1}\).
As shown in Figure 13-7, half the permutations generated by the previous method are duplicates.
Figure 13-7 Duplicate permutations
How can we remove these duplicates? A straightforward approach is to use a hash set to deduplicate the results. However, this is inelegant: branches that generate duplicate permutations are unnecessary and should be identified and pruned in advance, improving efficiency.
1. Pruning equal elements¶
In Figure 13-8, choosing \(1\) or \(\hat{1}\) in the first round is equivalent: every permutation produced under one choice is duplicated under the other. We should therefore prune \(\hat{1}\).
Similarly, after choosing \(2\) in the first round, choosing either \(1\) or \(\hat{1}\) in the second produces duplicate branches. Prune the second-round choice of \(\hat{1}\) as well.
In essence, within any one round of choices, we want to try only one of the elements with the same value.
Figure 13-8 Pruning duplicate permutations
2. Code implementation¶
Building on the previous solution, create a hash set duplicated in each round to record the values already tried in that round and prune repeated values:
permutations_ii.py
def backtrack(
state: list[int], choices: list[int], selected: list[bool], res: list[list[int]]
):
"""Backtracking: permutations II"""
# Record a solution when the state length equals the number of elements
if len(state) == len(choices):
res.append(list(state))
return
# Iterate over all choices
duplicated = set[int]()
for i, choice in enumerate(choices):
# Prune: do not reuse an element or choose the same value again at this depth
if not selected[i] and choice not in duplicated:
# Try: make a choice and update the state
duplicated.add(choice) # Record the chosen value
selected[i] = True
state.append(choice)
# Proceed to the next choice
backtrack(state, choices, selected, res)
# Backtrack: undo the choice and restore the previous state
selected[i] = False
state.pop()
def permutations_ii(nums: list[int]) -> list[list[int]]:
"""Permutations II"""
res = []
backtrack(state=[], choices=nums, selected=[False] * len(nums), res=res)
return res
permutations_ii.cpp
/* Backtracking: permutations II */
void backtrack(vector<int> &state, const vector<int> &choices, vector<bool> &selected, vector<vector<int>> &res) {
// Record a solution when the state length equals the number of elements
if (state.size() == choices.size()) {
res.push_back(state);
return;
}
// Iterate over all choices
unordered_set<int> duplicated;
for (int i = 0; i < choices.size(); i++) {
int choice = choices[i];
// Prune: do not reuse an element or choose the same value again at this depth
if (!selected[i] && duplicated.find(choice) == duplicated.end()) {
// Try: make a choice and update the state
duplicated.emplace(choice); // Record the chosen value
selected[i] = true;
state.push_back(choice);
// Proceed to the next choice
backtrack(state, choices, selected, res);
// Backtrack: undo the choice and restore the previous state
selected[i] = false;
state.pop_back();
}
}
}
/* Permutations II */
vector<vector<int>> permutationsII(vector<int> nums) {
vector<int> state;
vector<bool> selected(nums.size(), false);
vector<vector<int>> res;
backtrack(state, nums, selected, res);
return res;
}
permutations_ii.java
/* Backtracking: permutations II */
void backtrack(List<Integer> state, int[] choices, boolean[] selected, List<List<Integer>> res) {
// Record a solution when the state length equals the number of elements
if (state.size() == choices.length) {
res.add(new ArrayList<Integer>(state));
return;
}
// Iterate over all choices
Set<Integer> duplicated = new HashSet<Integer>();
for (int i = 0; i < choices.length; i++) {
int choice = choices[i];
// Prune: do not reuse an element or choose the same value again at this depth
if (!selected[i] && !duplicated.contains(choice)) {
// Try: make a choice and update the state
duplicated.add(choice); // Record the chosen value
selected[i] = true;
state.add(choice);
// Proceed to the next choice
backtrack(state, choices, selected, res);
// Backtrack: undo the choice and restore the previous state
selected[i] = false;
state.remove(state.size() - 1);
}
}
}
/* Permutations II */
List<List<Integer>> permutationsII(int[] nums) {
List<List<Integer>> res = new ArrayList<List<Integer>>();
backtrack(new ArrayList<Integer>(), nums, new boolean[nums.length], res);
return res;
}
permutations_ii.cs
/* Backtracking: permutations II */
void Backtrack(List<int> state, int[] choices, bool[] selected, List<List<int>> res) {
// Record a solution when the state length equals the number of elements
if (state.Count == choices.Length) {
res.Add(new List<int>(state));
return;
}
// Iterate over all choices
HashSet<int> duplicated = [];
for (int i = 0; i < choices.Length; i++) {
int choice = choices[i];
// Prune: do not reuse an element or choose the same value again at this depth
if (!selected[i] && !duplicated.Contains(choice)) {
// Try: make a choice and update the state
duplicated.Add(choice); // Record the chosen value
selected[i] = true;
state.Add(choice);
// Proceed to the next choice
Backtrack(state, choices, selected, res);
// Backtrack: undo the choice and restore the previous state
selected[i] = false;
state.RemoveAt(state.Count - 1);
}
}
}
/* Permutations II */
List<List<int>> PermutationsII(int[] nums) {
List<List<int>> res = [];
Backtrack([], nums, new bool[nums.Length], res);
return res;
}
permutations_ii.go
/* Backtracking: permutations II */
func backtrackII(state *[]int, choices *[]int, selected *[]bool, res *[][]int) {
// Record a solution when the state length equals the number of elements
if len(*state) == len(*choices) {
newState := append([]int{}, *state...)
*res = append(*res, newState)
}
// Iterate over all choices
duplicated := make(map[int]struct{}, 0)
for i := 0; i < len(*choices); i++ {
choice := (*choices)[i]
// Prune: do not reuse an element or choose the same value again at this depth
if _, ok := duplicated[choice]; !ok && !(*selected)[i] {
// Try: make a choice and update the state
// Record the chosen value
duplicated[choice] = struct{}{}
(*selected)[i] = true
*state = append(*state, choice)
// Proceed to the next choice
backtrackII(state, choices, selected, res)
// Backtrack: undo the choice and restore the previous state
(*selected)[i] = false
*state = (*state)[:len(*state)-1]
}
}
}
/* Permutations II */
func permutationsII(nums []int) [][]int {
res := make([][]int, 0)
state := make([]int, 0)
selected := make([]bool, len(nums))
backtrackII(&state, &nums, &selected, &res)
return res
}
permutations_ii.swift
/* Backtracking: permutations II */
func backtrack(state: inout [Int], choices: [Int], selected: inout [Bool], res: inout [[Int]]) {
// Record a solution when the state length equals the number of elements
if state.count == choices.count {
res.append(state)
return
}
// Iterate over all choices
var duplicated: Set<Int> = []
for (i, choice) in choices.enumerated() {
// Prune: do not reuse an element or choose the same value again at this depth
if !selected[i], !duplicated.contains(choice) {
// Try: make a choice and update the state
duplicated.insert(choice) // Record the chosen value
selected[i] = true
state.append(choice)
// Proceed to the next choice
backtrack(state: &state, choices: choices, selected: &selected, res: &res)
// Backtrack: undo the choice and restore the previous state
selected[i] = false
state.removeLast()
}
}
}
/* Permutations II */
func permutationsII(nums: [Int]) -> [[Int]] {
var state: [Int] = []
var selected = Array(repeating: false, count: nums.count)
var res: [[Int]] = []
backtrack(state: &state, choices: nums, selected: &selected, res: &res)
return res
}
permutations_ii.js
/* Backtracking: permutations II */
function backtrack(state, choices, selected, res) {
// Record a solution when the state length equals the number of elements
if (state.length === choices.length) {
res.push([...state]);
return;
}
// Iterate over all choices
const duplicated = new Set();
choices.forEach((choice, i) => {
// Prune: do not reuse an element or choose the same value again at this depth
if (!selected[i] && !duplicated.has(choice)) {
// Try: make a choice and update the state
duplicated.add(choice); // Record the chosen value
selected[i] = true;
state.push(choice);
// Proceed to the next choice
backtrack(state, choices, selected, res);
// Backtrack: undo the choice and restore the previous state
selected[i] = false;
state.pop();
}
});
}
/* Permutations II */
function permutationsII(nums) {
const res = [];
backtrack([], nums, Array(nums.length).fill(false), res);
return res;
}
permutations_ii.ts
/* Backtracking: permutations II */
function backtrack(
state: number[],
choices: number[],
selected: boolean[],
res: number[][]
): void {
// Record a solution when the state length equals the number of elements
if (state.length === choices.length) {
res.push([...state]);
return;
}
// Iterate over all choices
const duplicated = new Set();
choices.forEach((choice, i) => {
// Prune: do not reuse an element or choose the same value again at this depth
if (!selected[i] && !duplicated.has(choice)) {
// Try: make a choice and update the state
duplicated.add(choice); // Record the chosen value
selected[i] = true;
state.push(choice);
// Proceed to the next choice
backtrack(state, choices, selected, res);
// Backtrack: undo the choice and restore the previous state
selected[i] = false;
state.pop();
}
});
}
/* Permutations II */
function permutationsII(nums: number[]): number[][] {
const res: number[][] = [];
backtrack([], nums, Array(nums.length).fill(false), res);
return res;
}
permutations_ii.dart
/* Backtracking: permutations II */
void backtrack(
List<int> state,
List<int> choices,
List<bool> selected,
List<List<int>> res,
) {
// Record a solution when the state length equals the number of elements
if (state.length == choices.length) {
res.add(List.from(state));
return;
}
// Iterate over all choices
Set<int> duplicated = {};
for (int i = 0; i < choices.length; i++) {
int choice = choices[i];
// Prune: do not reuse an element or choose the same value again at this depth
if (!selected[i] && !duplicated.contains(choice)) {
// Try: make a choice and update the state
duplicated.add(choice); // Record the chosen value
selected[i] = true;
state.add(choice);
// Proceed to the next choice
backtrack(state, choices, selected, res);
// Backtrack: undo the choice and restore the previous state
selected[i] = false;
state.removeLast();
}
}
}
/* Permutations II */
List<List<int>> permutationsII(List<int> nums) {
List<List<int>> res = [];
backtrack([], nums, List.filled(nums.length, false), res);
return res;
}
permutations_ii.rs
/* Backtracking: permutations II */
fn backtrack(mut state: Vec<i32>, choices: &[i32], selected: &mut [bool], res: &mut Vec<Vec<i32>>) {
// Record a solution when the state length equals the number of elements
if state.len() == choices.len() {
res.push(state);
return;
}
// Iterate over all choices
let mut duplicated = HashSet::<i32>::new();
for i in 0..choices.len() {
let choice = choices[i];
// Prune: do not reuse an element or choose the same value again at this depth
if !selected[i] && !duplicated.contains(&choice) {
// Try: make a choice and update the state
duplicated.insert(choice); // Record the chosen value
selected[i] = true;
state.push(choice);
// Proceed to the next choice
backtrack(state.clone(), choices, selected, res);
// Backtrack: undo the choice and restore the previous state
selected[i] = false;
state.pop();
}
}
}
/* Permutations II */
fn permutations_ii(nums: &mut [i32]) -> Vec<Vec<i32>> {
let mut res = Vec::new();
backtrack(Vec::new(), nums, &mut vec![false; nums.len()], &mut res);
res
}
permutations_ii.c
/* Backtracking: permutations II */
void backtrack(int *state, int stateSize, int *choices, int choicesSize, bool *selected, int **res, int *resSize) {
// Record a solution when the state length equals the number of elements
if (stateSize == choicesSize) {
res[*resSize] = (int *)malloc(choicesSize * sizeof(int));
for (int i = 0; i < choicesSize; i++) {
res[*resSize][i] = state[i];
}
(*resSize)++;
return;
}
// Iterate over all choices
bool duplicated[MAX_SIZE] = {false};
for (int i = 0; i < choicesSize; i++) {
int choice = choices[i];
// Prune: do not reuse an element or choose the same value again at this depth
if (!selected[i] && !duplicated[choice]) {
// Try: make a choice and update the state
duplicated[choice] = true; // Record the chosen value
selected[i] = true;
state[stateSize] = choice;
// Proceed to the next choice
backtrack(state, stateSize + 1, choices, choicesSize, selected, res, resSize);
// Backtrack: undo the choice and restore the previous state
selected[i] = false;
}
}
}
/* Permutations II */
int **permutationsII(int *nums, int numsSize, int *returnSize) {
int *state = (int *)malloc(numsSize * sizeof(int));
bool *selected = (bool *)malloc(numsSize * sizeof(bool));
for (int i = 0; i < numsSize; i++) {
selected[i] = false;
}
int **res = (int **)malloc(MAX_SIZE * sizeof(int *));
*returnSize = 0;
backtrack(state, 0, nums, numsSize, selected, res, returnSize);
free(state);
free(selected);
return res;
}
permutations_ii.kt
/* Backtracking: permutations II */
fun backtrack(
state: MutableList<Int>,
choices: IntArray,
selected: BooleanArray,
res: MutableList<MutableList<Int>?>
) {
// Record a solution when the state length equals the number of elements
if (state.size == choices.size) {
res.add(state.toMutableList())
return
}
// Iterate over all choices
val duplicated = HashSet<Int>()
for (i in choices.indices) {
val choice = choices[i]
// Prune: do not reuse an element or choose the same value again at this depth
if (!selected[i] && !duplicated.contains(choice)) {
// Try: make a choice and update the state
duplicated.add(choice) // Record the chosen value
selected[i] = true
state.add(choice)
// Proceed to the next choice
backtrack(state, choices, selected, res)
// Backtrack: undo the choice and restore the previous state
selected[i] = false
state.removeAt(state.size - 1)
}
}
}
/* Permutations II */
fun permutationsII(nums: IntArray): MutableList<MutableList<Int>?> {
val res = mutableListOf<MutableList<Int>?>()
backtrack(mutableListOf(), nums, BooleanArray(nums.size), res)
return res
}
permutations_ii.rb
### Backtracking: permutations II ###
def backtrack(state, choices, selected, res)
# Record a solution when the state length equals the number of elements
if state.length == choices.length
res << state.dup
return
end
# Iterate over all choices
duplicated = Set.new
choices.each_with_index do |choice, i|
# Prune: do not reuse an element or choose the same value again at this depth
if !selected[i] && !duplicated.include?(choice)
# Try: make a choice and update the state
duplicated.add(choice)
selected[i] = true
state << choice
# Proceed to the next choice
backtrack(state, choices, selected, res)
# Backtrack: undo the choice and restore the previous state
selected[i] = false
state.pop
end
end
end
### Permutations II ###
def permutations_ii(nums)
res = []
backtrack([], nums, Array.new(nums.length, false), res)
res
end
Visualize execution
If all elements are distinct, \(n\) elements have \(n!\) permutations, where the exclamation mark denotes factorial. Recording each result requires copying a list of length \(n\), taking \(O(n)\) time. The time complexity is therefore \(O(n!n)\).
The maximum recursion depth is \(n\), requiring \(O(n)\) space for stack frames. The array selected uses \(O(n)\) space. At most \(n\) duplicated sets exist at once, using \(O(n^2)\) space. The space complexity is therefore \(O(n^2)\).
3. Comparing the two pruning methods¶
Although both selected and duplicated are used for pruning, they serve different purposes.
- Pruning repeated selections: There is only one
selectedarray throughout the search. It records which elements are in the current state, preventing the same element from appearing twice instate. - Pruning equal elements: Each round of choices (each call to
backtrack) has its ownduplicatedset. It records the values already chosen in that round'sforloop, ensuring that equal elements are tried only once in that round.
Figure 13-9 shows the scope of each pruning condition. Each node represents a choice, and the nodes along a path from root to leaf form a permutation.
Figure 13-9 Scope of the two pruning conditions