Card 04/ 09
Backtracking in Python, Java and TypeScript
Subsets and permutations on one shared path, copying it only when a solution is recorded.
A backtracking search is a recursive function over one shared path, with a copy taken only when a complete solution is recorded. The listings below generate the subsets and the permutations of 1 2 3 in each language, with the same structure: record a copy at a leaf, otherwise choose, search and undo.
Subsets and permutations by backtracking, in each language
def subsets(items: list[int]) -> list[list[int]]:
result: list[list[int]] = []
path: list[int] = []
def search(i: int) -> None:
if i == len(items):
result.append(list(path))
return
path.append(items[i])
search(i + 1)
path.pop()
search(i + 1)
search(0)
return result
def permutations(items: list[int]) -> list[list[int]]:
result: list[list[int]] = []
path: list[int] = []
used = [False] * len(items)
def search() -> None:
if len(path) == len(items):
result.append(list(path))
return
for i, item in enumerate(items):
if used[i]:
continue
used[i] = True
path.append(item)
search()
path.pop()
used[i] = False
search()
return result
def show(lists: list[list[int]]) -> str:
return " ".join("[" + " ".join(map(str, values)) + "]" for values in lists)
print("subsets:", show(subsets([1, 2, 3])))
print("permutations:", show(permutations([1, 2, 3])))subsets: [1 2 3] [1 2] [1 3] [1] [2 3] [2] [3] []
permutations: [1 2 3] [1 3 2] [2 1 3] [2 3 1] [3 1 2] [3 2 1]import java.util.ArrayList;
import java.util.List;
import java.util.stream.Collectors;
public class BacktrackingCode {
static void subsets(int[] items, int i, List<Integer> path, List<List<Integer>> result) {
if (i == items.length) {
result.add(new ArrayList<>(path));
return;
}
path.add(items[i]);
subsets(items, i + 1, path, result);
path.remove(path.size() - 1);
subsets(items, i + 1, path, result);
}
static void permutations(int[] items, boolean[] used, List<Integer> path, List<List<Integer>> result) {
if (path.size() == items.length) {
result.add(new ArrayList<>(path));
return;
}
for (int i = 0; i < items.length; i++) {
if (used[i]) {
continue;
}
used[i] = true;
path.add(items[i]);
permutations(items, used, path, result);
path.remove(path.size() - 1);
used[i] = false;
}
}
static String show(List<List<Integer>> lists) {
return lists.stream()
.map(values -> "[" + values.stream().map(String::valueOf).collect(Collectors.joining(" ")) + "]")
.collect(Collectors.joining(" "));
}
public static void main(String[] args) {
int[] items = {1, 2, 3};
List<List<Integer>> subsets = new ArrayList<>();
subsets(items, 0, new ArrayList<>(), subsets);
System.out.println("subsets: " + show(subsets));
List<List<Integer>> permutations = new ArrayList<>();
permutations(items, new boolean[items.length], new ArrayList<>(), permutations);
System.out.println("permutations: " + show(permutations));
}
}subsets: [1 2 3] [1 2] [1 3] [1] [2 3] [2] [3] []
permutations: [1 2 3] [1 3 2] [2 1 3] [2 3 1] [3 1 2] [3 2 1]function subsets(items: number[]): number[][] {
const result: number[][] = [];
const path: number[] = [];
const search = (i: number): void => {
if (i === items.length) {
result.push([...path]);
return;
}
path.push(items[i]);
search(i + 1);
path.pop();
search(i + 1);
};
search(0);
return result;
}
function permutations(items: number[]): number[][] {
const result: number[][] = [];
const path: number[] = [];
const used = items.map(() => false);
const search = (): void => {
if (path.length === items.length) {
result.push([...path]);
return;
}
items.forEach((item, i) => {
if (used[i]) {
return;
}
used[i] = true;
path.push(item);
search();
path.pop();
used[i] = false;
});
};
search();
return result;
}
const show = (lists: number[][]): string => lists.map((values) => `[${values.join(" ")}]`).join(" ");
console.log(`subsets: ${show(subsets([1, 2, 3]))}`);
console.log(`permutations: ${show(permutations([1, 2, 3]))}`);subsets: [1 2 3] [1 2] [1 3] [1] [2 3] [2] [3] []
permutations: [1 2 3] [1 3 2] [2 1 3] [2 3 1] [3 1 2] [3 2 1]All three printed the same eight subsets and six permutations. The highlighted lines come in pairs: in each function, one records a copy of the path and the other undoes the last choice.
The copy is list(path) in Python, new ArrayList<>(path) in Java and [...path] in TypeScript. Each makes a new list holding the same items, so the recorded solution no longer changes when the path does. Recording the path itself stores the same list eight times, and a run that did so printed eight empty lists, because by the time the search finished every choice had been undone. The undo is pop() in Python and TypeScript and remove(path.size() - 1) in Java; Java's remove(int) removes by index, which is why it is given the last index rather than the item.
The subsets function makes two calls per item, one after taking it and one after skipping it. The permutations function loops over every item and skips the used ones, with the used flags undone together with the path. Python's itertools.combinations and itertools.permutations generate both without any of this, and are the right call when the task is only to list them; the hand-written search earns its place once rules prune the tree, as Pruning a Branch as Soon as It Breaks a Rule shows.
← → move through sections and cards