PK

PKBytes

Explore tracks
Chapter 20: Backtracking, Constraint Search and State Space
20.02Intermediate6 topics18 min5 interactive animations

Subset and permutation generation

Generating subsets, the power set, subsequences, all permutations, unique permutations of multisets and combinations, with the exact loop shapes and counts for each.

Learning goals

  • Write the start-index loop for subsets and combinations
  • Write the used-array loop for permutations
  • Skip duplicates correctly by sorting first
  • State the number of results for each family

Prerequisites

The backtracking methodBit manipulation
20.02.1

Subsets

To list all subsets of an array, record the current path at *every* node, and let each node extend the path with elements that come later in the array. Passing i + 1 as the next start index guarantees each subset is built in increasing index order, so no subset appears twice. n elements give 2^n subsets.

In the animation every node is a subset and every edge adds one value. Try the “Four values (16 subsets)” preset to see the tree double with each extra element.

Java
1static List<List<Integer>> subsets(int[] a) {
2    List<List<Integer>> out = new ArrayList<>();
3    collect(a, 0, new ArrayList<>(), out);
4    return out;
5}
6private static void collect(int[] a, int start, List<Integer> path, List<List<Integer>> out) {
7    out.add(new ArrayList<>(path));                           // every partial solution is a subset
8    for (int i = start; i < a.length; i++) {
9        path.add(a[i]);
10        collect(a, i + 1, path, out);
11        path.remove(path.size() - 1);
12    }
13}

Best

O(n · 2^n)

Average

O(n · 2^n)

Worst

O(n · 2^n)

Space

O(n) recursion, plus the output

Subsets (power set) by backtracking

Interactive · edit the input

Your input

Try

partial solution

[]

solutions found (0)

none yet
Setup

Each value is either in the subset or not. Backtracking builds the subsets one value at a time: choose a value, explore everything after it, then unchoose. 3 values give 2^3 = 8 subsets.

Step 1 / 32
Java
1static void subsets(int[] a, int start, List<Integer> path, List<List<Integer>> out) {
2    out.add(new ArrayList<>(path));                          // every partial solution is a subset
3    for (int i = start; i < a.length; i++) {
4        path.add(a[i]);                                      // choose
5        subsets(a, i + 1, path, out);                        // explore
6        path.remove(path.size() - 1);                        // unchoose
7    }
8}

Live state

depth

0

solutions

0

No condition evaluated on this step

Call stack (top first)

  1. empty
Execution trace (dry run table)Show 32 steps
StepLineStateWhat happens
1L1depth=0 solutions=0Each value is either in the subset or not. Backtracking builds the subsets one value at a time: choose a value, explore everything after it, then unchoose. 3 values give 2^3 = 8 subsets.
2L1depth=1 solutions=0Explore [].
3L2depth=1 solutions=1Record []: every partial solution counts here.
4L4depth=1 solutions=1Choose 1.
5L1depth=2 solutions=1Explore [1].
6L2depth=2 solutions=2Record [1]: every partial solution counts here.
7L4depth=2 solutions=2Choose 2.
8L1depth=3 solutions=2Explore [1, 2].
9L2depth=3 solutions=3Record [1, 2]: every partial solution counts here.
10L4depth=3 solutions=3Choose 3.
11L1depth=4 solutions=3Explore [1, 2, 3].
12L2depth=4 solutions=4Record [1, 2, 3]: every partial solution counts here.
13L6depth=3 solutions=4Unchoose 3: back to [1, 2].
14L6depth=2 solutions=4Unchoose 2: back to [1].
15L4depth=2 solutions=4Choose 3.
16L1depth=3 solutions=4Explore [1, 3].
17L2depth=3 solutions=5Record [1, 3]: every partial solution counts here.
18L6depth=2 solutions=5Unchoose 3: back to [1].
19L6depth=1 solutions=5Unchoose 1: back to [].
20L4depth=1 solutions=5Choose 2.
21L1depth=2 solutions=5Explore [2].
22L2depth=2 solutions=6Record [2]: every partial solution counts here.
23L4depth=2 solutions=6Choose 3.
24L1depth=3 solutions=6Explore [2, 3].
25L2depth=3 solutions=7Record [2, 3]: every partial solution counts here.
26L6depth=2 solutions=7Unchoose 3: back to [2].
27L6depth=1 solutions=7Unchoose 2: back to [].
28L4depth=1 solutions=7Choose 3.
29L1depth=2 solutions=7Explore [3].
30L2depth=2 solutions=8Record [3]: every partial solution counts here.
31L6depth=1 solutions=8Unchoose 3: back to [].
32L8solutions=8 nodes=8 return=[[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]Search finished: 8 solutions, 7 choices tried. Backtracking explores every branch the pruning rules allow.
20.02.2

Power set

The **power set** is the set of all subsets, 2^n of them. There is a second way to generate it without recursion: every subset of n elements corresponds to an n-bit number, where bit i says whether element i is included. Counting from 0 to 2^n − 1 visits every subset exactly once (this is the technique of Chapter 6, Bit Manipulation).

The bitmask loop is shorter and has no stack, but it works only for n up to about 30 (an int mask) or 62 (a long), and it cannot prune. Backtracking can stop early; the mask loop cannot. The existing animation “Enumerate subsets” in Chapter 6 shows the masks.

Java
1static List<List<Integer>> powerSet(int[] a) {
2    int n = a.length;
3    List<List<Integer>> out = new ArrayList<>();
4    for (int mask = 0; mask < (1 << n); mask++) {             // each mask is one subset
5        List<Integer> subset = new ArrayList<>();
6        for (int i = 0; i < n; i++) if ((mask >> i & 1) == 1) subset.add(a[i]);
7        out.add(subset);
8    }
9    return out;
10}

Enumerate all subsets with a bitmask

Interactive · edit the input

Your input

Try

int[] arr · length 3

5
7
9
012
In the subset (bit is 1)

subsets so far

empty
Setup

3 items give 2^3 = 8 subsets. Every number from 0 to 7 is one choice: bit i says whether item i is in.

Step 1 / 10
Java
1int n = items.length;
2for (int mask = 0; mask < (1 << n); mask++) {
3    List<Integer> subset = new ArrayList<>();
4    for (int i = 0; i < n; i++) {
5        if ((mask & (1 << i)) != 0) {      // is bit i set?
6            subset.add(items[i]);
7        }
8    }
9    print(subset);
10}

Live state

0 subsets

n

3

2^n

8

No condition evaluated on this step
Execution trace (dry run table)Show 10 steps
StepLineStateWhat happens
1L2n=3 2^n=83 items give 2^3 = 8 subsets. Every number from 0 to 7 is one choice: bit i says whether item i is in.
2L5mask=0 subset={}mask 0 has no bits set: the empty subset.
3L5mask=1 subset={5}mask 1 = 001 in binary. Bits 0 are set, so the subset is {5}.
4L5mask=2 subset={7}mask 2 = 010 in binary. Bits 1 are set, so the subset is {7}.
5L5mask=3 subset={5, 7}mask 3 = 011 in binary. Bits 0, 1 are set, so the subset is {5, 7}.
6L5mask=4 subset={9}mask 4 = 100 in binary. Bits 2 are set, so the subset is {9}.
7L5mask=5 subset={5, 9}mask 5 = 101 in binary. Bits 0, 2 are set, so the subset is {5, 9}.
8L5mask=6 subset={7, 9}mask 6 = 110 in binary. Bits 1, 2 are set, so the subset is {7, 9}.
9L5mask=7 subset={5, 7, 9}mask 7 = 111 in binary. Bits 0, 1, 2 are set, so the subset is {5, 7, 9}.
10L10subsets=88 subsets generated in O(2^n · n). This only works for small n (up to about 20-25), because the count doubles with every item.
20.02.3

Subsequences

A **subsequence** keeps the original order but may skip elements; a subset ignores order. For an array or string with distinct positions, the subsequences are exactly the subsets of the *positions*, so the same code generates them: choose indices in increasing order. A string of length n has 2^n subsequences (counting the empty one); duplicates appear if the string has repeated letters, such as the two a's in "aab".

To list distinct subsequences of a string with repeats, sort the characters and skip a character equal to the previous one at the same level (the rule used for unique permutations below), or collect results in a Set.

Java
1static List<String> subsequences(String s) {
2    List<String> out = new ArrayList<>();
3    pick(s, 0, new StringBuilder(), out);
4    return out;
5}
6private static void pick(String s, int start, StringBuilder sb, List<String> out) {
7    out.add(sb.toString());                                   // "" is a subsequence too
8    for (int i = start; i < s.length(); i++) {
9        sb.append(s.charAt(i));                               // choose
10        pick(s, i + 1, sb, out);                              // explore
11        sb.deleteCharAt(sb.length() - 1);                     // unchoose
12    }
13}
20.02.4

All permutations

A permutation uses every element exactly once, so at each level the loop tries *every* index that is not yet used. A used[] array tracks which ones are on the path. n distinct elements have n! permutations; the tree has n + n(n−1) + … nodes, about e·n!.

The animation lists the 6 permutations of {1, 2, 3} in a tree of 31 nodes: 16 real nodes (1 + 3 + 6 + 6) and 15 rejected ✗ options, which show what the used[i] check prevents. Four values already produce 24 permutations; the factorial growth is why exhaustive search stops being practical past about n = 10 or 11.

Java
1static List<List<Integer>> permutations(int[] a) {
2    List<List<Integer>> out = new ArrayList<>();
3    arrange(a, new boolean[a.length], new ArrayList<>(), out);
4    return out;
5}
6private static void arrange(int[] a, boolean[] used, List<Integer> path, List<List<Integer>> out) {
7    if (path.size() == a.length) { out.add(new ArrayList<>(path)); return; }
8    for (int i = 0; i < a.length; i++) {
9        if (used[i]) continue;
10        used[i] = true; path.add(a[i]);
11        arrange(a, used, path, out);
12        path.remove(path.size() - 1); used[i] = false;
13    }
14}

Best

O(n · n!)

Average

O(n · n!)

Worst

O(n · n!)

Space

O(n) recursion, plus the output

Permutations, including unique permutations with duplicates

Interactive · edit the input

Your input

Try

partial solution

[]

solutions found (0)

none yet
Setup

at every level try each value not yet used (the used[] array is the undo state). 3 values have 3! = 6 orderings.

Step 1 / 69
Java
1static void permute(int[] a, boolean[] used, List<Integer> path, List<List<Integer>> out, boolean unique) {   // sort a first when unique
2    if (path.size() == a.length) { out.add(new ArrayList<>(path)); return; }
3    for (int i = 0; i < a.length; i++) {
4        if (used[i]) continue;                                            // already on the path
5        if (unique && i > 0 && a[i] == a[i - 1] && !used[i - 1]) continue;   // a twin of the previous value, which is free
6        used[i] = true; path.add(a[i]);                                   // choose
7        permute(a, used, path, out, unique);                              // explore
8        path.remove(path.size() - 1); used[i] = false;                    // unchoose
9    }
10}

Live state

depth

0

solutions

0

No condition evaluated on this step

Call stack (top first)

  1. empty
Execution trace (dry run table)Show 69 steps
StepLineStateWhat happens
1L1depth=0 solutions=0at every level try each value not yet used (the used[] array is the undo state). 3 values have 3! = 6 orderings.
2L1depth=1 solutions=0Explore [].
3L6depth=1 solutions=0Choose 1.
4L1depth=2 solutions=0Explore [1].
5L4depth=3 solutions=0Reject 1: already on the path.
6L6depth=2 solutions=0Choose 2.
7L1depth=3 solutions=0Explore [1, 2].
8L4depth=4 solutions=0Reject 1: already on the path.
9L4depth=4 solutions=0Reject 2: already on the path.
10L6depth=3 solutions=0Choose 3.
11L1depth=4 solutions=0Explore [1, 2, 3].
12L2depth=4 solutions=1Complete and valid: record [1, 2, 3].
13L8depth=3 solutions=1Unchoose 3: back to [1, 2].
14L8depth=2 solutions=1Unchoose 2: back to [1].
15L6depth=2 solutions=1Choose 3.
16L1depth=3 solutions=1Explore [1, 3].
17L4depth=4 solutions=1Reject 1: already on the path.
18L6depth=3 solutions=1Choose 2.
19L1depth=4 solutions=1Explore [1, 3, 2].
20L2depth=4 solutions=2Complete and valid: record [1, 3, 2].
21L8depth=3 solutions=2Unchoose 2: back to [1, 3].
22L4depth=4 solutions=2Reject 3: already on the path.
23L8depth=2 solutions=2Unchoose 3: back to [1].
24L8depth=1 solutions=2Unchoose 1: back to [].
25L6depth=1 solutions=2Choose 2.
26L1depth=2 solutions=2Explore [2].
27L6depth=2 solutions=2Choose 1.
28L1depth=3 solutions=2Explore [2, 1].
29L4depth=4 solutions=2Reject 1: already on the path.
30L4depth=4 solutions=2Reject 2: already on the path.
31L6depth=3 solutions=2Choose 3.
32L1depth=4 solutions=2Explore [2, 1, 3].
33L2depth=4 solutions=3Complete and valid: record [2, 1, 3].
34L8depth=3 solutions=3Unchoose 3: back to [2, 1].
35L8depth=2 solutions=3Unchoose 1: back to [2].
36L4depth=3 solutions=3Reject 2: already on the path.
37L6depth=2 solutions=3Choose 3.
38L1depth=3 solutions=3Explore [2, 3].
39L6depth=3 solutions=3Choose 1.
40L1depth=4 solutions=3Explore [2, 3, 1].
41L2depth=4 solutions=4Complete and valid: record [2, 3, 1].
42L8depth=3 solutions=4Unchoose 1: back to [2, 3].
43L4depth=4 solutions=4Reject 2: already on the path.
44L4depth=4 solutions=4Reject 3: already on the path.
45L8depth=2 solutions=4Unchoose 3: back to [2].
46L8depth=1 solutions=4Unchoose 2: back to [].
47L6depth=1 solutions=4Choose 3.
48L1depth=2 solutions=4Explore [3].
49L6depth=2 solutions=4Choose 1.
50L1depth=3 solutions=4Explore [3, 1].
51L4depth=4 solutions=4Reject 1: already on the path.
52L6depth=3 solutions=4Choose 2.
53L1depth=4 solutions=4Explore [3, 1, 2].
54L2depth=4 solutions=5Complete and valid: record [3, 1, 2].
55L8depth=3 solutions=5Unchoose 2: back to [3, 1].
56L4depth=4 solutions=5Reject 3: already on the path.
57L8depth=2 solutions=5Unchoose 1: back to [3].
58L6depth=2 solutions=5Choose 2.
59L1depth=3 solutions=5Explore [3, 2].
60L6depth=3 solutions=5Choose 1.
61L1depth=4 solutions=5Explore [3, 2, 1].
62L2depth=4 solutions=6Complete and valid: record [3, 2, 1].
63L8depth=3 solutions=6Unchoose 1: back to [3, 2].
64L4depth=4 solutions=6Reject 2: already on the path.
65L4depth=4 solutions=6Reject 3: already on the path.
66L8depth=2 solutions=6Unchoose 2: back to [3].
67L4depth=3 solutions=6Reject 3: already on the path.
68L8depth=1 solutions=6Unchoose 3: back to [].
69L10solutions=6 nodes=31 return=[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]Search finished: 6 solutions, 30 choices tried. Backtracking explores every branch the pruning rules allow.
20.02.5

Unique permutations with duplicates

If the input has repeated values, plain permutation code lists identical results more than once: for {1, 1, 2} it produces 6 lists but only 3 are different. The fix is to **sort** the array and skip an element that equals the previous one *when the previous one is not currently used*: that means we are about to start a branch that a twin already explored at this level.

Choose “Duplicates: repeated results” and then “Duplicates: unique only” in the animation. The same input needs 31 nodes without the rule and 19 with it, and the answers shrink from 6 to the 3 distinct arrangements [1, 1, 2], [1, 2, 1], [2, 1, 1].

Java
1static List<List<Integer>> uniquePermutations(int[] a) {
2    int[] sorted = a.clone(); Arrays.sort(sorted);
3    List<List<Integer>> out = new ArrayList<>();
4    arrangeUnique(sorted, new boolean[sorted.length], new ArrayList<>(), out);
5    return out;
6}
7private static void arrangeUnique(int[] a, boolean[] used, List<Integer> path, List<List<Integer>> out) {
8    if (path.size() == a.length) { out.add(new ArrayList<>(path)); return; }
9    for (int i = 0; i < a.length; i++) {
10        if (used[i]) continue;
11        if (i > 0 && a[i] == a[i - 1] && !used[i - 1]) continue;  // a twin of the previous value, which is free
12        used[i] = true; path.add(a[i]);
13        arrangeUnique(a, used, path, out);
14        path.remove(path.size() - 1); used[i] = false;
15    }
16}

Permutations, including unique permutations with duplicates

Interactive · edit the input

Your input

Try

partial solution

[]

solutions found (0)

none yet
Setup

at every level try each value not yet used (the used[] array is the undo state). 3 values have 3! = 6 orderings.

Step 1 / 69
Java
1static void permute(int[] a, boolean[] used, List<Integer> path, List<List<Integer>> out, boolean unique) {   // sort a first when unique
2    if (path.size() == a.length) { out.add(new ArrayList<>(path)); return; }
3    for (int i = 0; i < a.length; i++) {
4        if (used[i]) continue;                                            // already on the path
5        if (unique && i > 0 && a[i] == a[i - 1] && !used[i - 1]) continue;   // a twin of the previous value, which is free
6        used[i] = true; path.add(a[i]);                                   // choose
7        permute(a, used, path, out, unique);                              // explore
8        path.remove(path.size() - 1); used[i] = false;                    // unchoose
9    }
10}

Live state

depth

0

solutions

0

No condition evaluated on this step

Call stack (top first)

  1. empty
Execution trace (dry run table)Show 69 steps
StepLineStateWhat happens
1L1depth=0 solutions=0at every level try each value not yet used (the used[] array is the undo state). 3 values have 3! = 6 orderings.
2L1depth=1 solutions=0Explore [].
3L6depth=1 solutions=0Choose 1.
4L1depth=2 solutions=0Explore [1].
5L4depth=3 solutions=0Reject 1: already on the path.
6L6depth=2 solutions=0Choose 2.
7L1depth=3 solutions=0Explore [1, 2].
8L4depth=4 solutions=0Reject 1: already on the path.
9L4depth=4 solutions=0Reject 2: already on the path.
10L6depth=3 solutions=0Choose 3.
11L1depth=4 solutions=0Explore [1, 2, 3].
12L2depth=4 solutions=1Complete and valid: record [1, 2, 3].
13L8depth=3 solutions=1Unchoose 3: back to [1, 2].
14L8depth=2 solutions=1Unchoose 2: back to [1].
15L6depth=2 solutions=1Choose 3.
16L1depth=3 solutions=1Explore [1, 3].
17L4depth=4 solutions=1Reject 1: already on the path.
18L6depth=3 solutions=1Choose 2.
19L1depth=4 solutions=1Explore [1, 3, 2].
20L2depth=4 solutions=2Complete and valid: record [1, 3, 2].
21L8depth=3 solutions=2Unchoose 2: back to [1, 3].
22L4depth=4 solutions=2Reject 3: already on the path.
23L8depth=2 solutions=2Unchoose 3: back to [1].
24L8depth=1 solutions=2Unchoose 1: back to [].
25L6depth=1 solutions=2Choose 2.
26L1depth=2 solutions=2Explore [2].
27L6depth=2 solutions=2Choose 1.
28L1depth=3 solutions=2Explore [2, 1].
29L4depth=4 solutions=2Reject 1: already on the path.
30L4depth=4 solutions=2Reject 2: already on the path.
31L6depth=3 solutions=2Choose 3.
32L1depth=4 solutions=2Explore [2, 1, 3].
33L2depth=4 solutions=3Complete and valid: record [2, 1, 3].
34L8depth=3 solutions=3Unchoose 3: back to [2, 1].
35L8depth=2 solutions=3Unchoose 1: back to [2].
36L4depth=3 solutions=3Reject 2: already on the path.
37L6depth=2 solutions=3Choose 3.
38L1depth=3 solutions=3Explore [2, 3].
39L6depth=3 solutions=3Choose 1.
40L1depth=4 solutions=3Explore [2, 3, 1].
41L2depth=4 solutions=4Complete and valid: record [2, 3, 1].
42L8depth=3 solutions=4Unchoose 1: back to [2, 3].
43L4depth=4 solutions=4Reject 2: already on the path.
44L4depth=4 solutions=4Reject 3: already on the path.
45L8depth=2 solutions=4Unchoose 3: back to [2].
46L8depth=1 solutions=4Unchoose 2: back to [].
47L6depth=1 solutions=4Choose 3.
48L1depth=2 solutions=4Explore [3].
49L6depth=2 solutions=4Choose 1.
50L1depth=3 solutions=4Explore [3, 1].
51L4depth=4 solutions=4Reject 1: already on the path.
52L6depth=3 solutions=4Choose 2.
53L1depth=4 solutions=4Explore [3, 1, 2].
54L2depth=4 solutions=5Complete and valid: record [3, 1, 2].
55L8depth=3 solutions=5Unchoose 2: back to [3, 1].
56L4depth=4 solutions=5Reject 3: already on the path.
57L8depth=2 solutions=5Unchoose 1: back to [3].
58L6depth=2 solutions=5Choose 2.
59L1depth=3 solutions=5Explore [3, 2].
60L6depth=3 solutions=5Choose 1.
61L1depth=4 solutions=5Explore [3, 2, 1].
62L2depth=4 solutions=6Complete and valid: record [3, 2, 1].
63L8depth=3 solutions=6Unchoose 1: back to [3, 2].
64L4depth=4 solutions=6Reject 2: already on the path.
65L4depth=4 solutions=6Reject 3: already on the path.
66L8depth=2 solutions=6Unchoose 2: back to [3].
67L4depth=3 solutions=6Reject 3: already on the path.
68L8depth=1 solutions=6Unchoose 3: back to [].
69L10solutions=6 nodes=31 return=[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]Search finished: 6 solutions, 30 choices tried. Backtracking explores every branch the pruning rules allow.
20.02.6

Combinations

A **combination** of size k is a subset with exactly k elements: C(n, k) = n! / (k!(n−k)!) of them. Generate them with the same start-index loop as subsets, but record a result only when the path reaches size k, and prune when too few values remain. C(5, 3) = 10.

Run the “k = 4 of 5” and “k = n” presets: C(5, 4) = 5 and C(3, 3) = 1. Combinations ignore order (1, 2 and 2, 1 are the same combination), which is why the loop moves forward only.

Java
1static List<List<Integer>> choose(int n, int k) {
2    List<List<Integer>> out = new ArrayList<>();
3    pickK(n, k, 1, new ArrayList<>(), out);
4    return out;
5}
6private static void pickK(int n, int k, int start, List<Integer> path, List<List<Integer>> out) {
7    if (path.size() == k) { out.add(new ArrayList<>(path)); return; }
8    for (int v = start; v <= n - (k - path.size()) + 1; v++) {    // stop when too few values remain
9        path.add(v);
10        pickK(n, k, v + 1, path, out);
11        path.remove(path.size() - 1);
12    }
13}

Combinations of size k, with and without pruning

Interactive · edit the input

Your input

Try

partial solution

[]

solutions found (0)

none yet
Setup

Choose 3 of 5 values in increasing order so each combination appears once. Pruning is on: a branch is abandoned as soon as the remaining values cannot fill the combination.

Step 1 / 74
Java
1static void combine(int[] a, int k, int start, List<Integer> path, List<List<Integer>> out, boolean prune) {
2    if (path.size() == k) { out.add(new ArrayList<>(path)); return; }
3    for (int i = start; i < a.length; i++) {
4        if (prune && path.size() + (a.length - i) < k) break;      // too few values left to reach size k
5        path.add(a[i]);                                           // choose
6        combine(a, k, i + 1, path, out, prune);                   // explore
7        path.remove(path.size() - 1);                             // unchoose
8    }
9}

Live state

depth

0

solutions

0

No condition evaluated on this step

Call stack (top first)

  1. empty
Execution trace (dry run table)Show 74 steps
StepLineStateWhat happens
1L1depth=0 solutions=0Choose 3 of 5 values in increasing order so each combination appears once. Pruning is on: a branch is abandoned as soon as the remaining values cannot fill the combination.
2L1depth=1 solutions=0Explore [].
3L5depth=1 solutions=0Choose 1.
4L1depth=2 solutions=0Explore [1].
5L5depth=2 solutions=0Choose 2.
6L1depth=3 solutions=0Explore [1, 2].
7L5depth=3 solutions=0Choose 3.
8L1depth=4 solutions=0Explore [1, 2, 3].
9L2depth=4 solutions=1Complete and valid: record [1, 2, 3].
10L7depth=3 solutions=1Unchoose 3: back to [1, 2].
11L5depth=3 solutions=1Choose 4.
12L1depth=4 solutions=1Explore [1, 2, 4].
13L2depth=4 solutions=2Complete and valid: record [1, 2, 4].
14L7depth=3 solutions=2Unchoose 4: back to [1, 2].
15L5depth=3 solutions=2Choose 5.
16L1depth=4 solutions=2Explore [1, 2, 5].
17L2depth=4 solutions=3Complete and valid: record [1, 2, 5].
18L7depth=3 solutions=3Unchoose 5: back to [1, 2].
19L7depth=2 solutions=3Unchoose 2: back to [1].
20L5depth=2 solutions=3Choose 3.
21L1depth=3 solutions=3Explore [1, 3].
22L5depth=3 solutions=3Choose 4.
23L1depth=4 solutions=3Explore [1, 3, 4].
24L2depth=4 solutions=4Complete and valid: record [1, 3, 4].
25L7depth=3 solutions=4Unchoose 4: back to [1, 3].
26L5depth=3 solutions=4Choose 5.
27L1depth=4 solutions=4Explore [1, 3, 5].
28L2depth=4 solutions=5Complete and valid: record [1, 3, 5].
29L7depth=3 solutions=5Unchoose 5: back to [1, 3].
30L7depth=2 solutions=5Unchoose 3: back to [1].
31L5depth=2 solutions=5Choose 4.
32L1depth=3 solutions=5Explore [1, 4].
33L5depth=3 solutions=5Choose 5.
34L1depth=4 solutions=5Explore [1, 4, 5].
35L2depth=4 solutions=6Complete and valid: record [1, 4, 5].
36L7depth=3 solutions=6Unchoose 5: back to [1, 4].
37L7depth=2 solutions=6Unchoose 4: back to [1].
38L4depth=3 solutions=6Reject 5: only 1 value left but 2 more are needed.
39L7depth=1 solutions=6Unchoose 1: back to [].
40L5depth=1 solutions=6Choose 2.
41L1depth=2 solutions=6Explore [2].
42L5depth=2 solutions=6Choose 3.
43L1depth=3 solutions=6Explore [2, 3].
44L5depth=3 solutions=6Choose 4.
45L1depth=4 solutions=6Explore [2, 3, 4].
46L2depth=4 solutions=7Complete and valid: record [2, 3, 4].
47L7depth=3 solutions=7Unchoose 4: back to [2, 3].
48L5depth=3 solutions=7Choose 5.
49L1depth=4 solutions=7Explore [2, 3, 5].
50L2depth=4 solutions=8Complete and valid: record [2, 3, 5].
51L7depth=3 solutions=8Unchoose 5: back to [2, 3].
52L7depth=2 solutions=8Unchoose 3: back to [2].
53L5depth=2 solutions=8Choose 4.
54L1depth=3 solutions=8Explore [2, 4].
55L5depth=3 solutions=8Choose 5.
56L1depth=4 solutions=8Explore [2, 4, 5].
57L2depth=4 solutions=9Complete and valid: record [2, 4, 5].
58L7depth=3 solutions=9Unchoose 5: back to [2, 4].
59L7depth=2 solutions=9Unchoose 4: back to [2].
60L4depth=3 solutions=9Reject 5: only 1 value left but 2 more are needed.
61L7depth=1 solutions=9Unchoose 2: back to [].
62L5depth=1 solutions=9Choose 3.
63L1depth=2 solutions=9Explore [3].
64L5depth=2 solutions=9Choose 4.
65L1depth=3 solutions=9Explore [3, 4].
66L5depth=3 solutions=9Choose 5.
67L1depth=4 solutions=9Explore [3, 4, 5].
68L2depth=4 solutions=10Complete and valid: record [3, 4, 5].
69L7depth=3 solutions=10Unchoose 5: back to [3, 4].
70L7depth=2 solutions=10Unchoose 4: back to [3].
71L4depth=3 solutions=10Reject 5: only 1 value left but 2 more are needed.
72L7depth=1 solutions=10Unchoose 3: back to [].
73L4depth=2 solutions=10Reject 4: only 2 values left but 3 more are needed.
74L9solutions=10 nodes=24 return=[[1, 2, 3], [1, 2, 4], [1, 2, 5], [1, 3, 4], [1, 3, 5], [1, 4, 5], [2, 3, 4], [2, 3, 5], [2, 4, 5], [3, 4, 5]]Search finished: 10 solutions, 23 choices tried. Backtracking explores every branch the pruning rules allow.

Practice ladder

Now try it yourself

Easy

  • Subsets
  • Letter Case Permutation

Medium

  • Permutations II
  • Combinations
  • Subsets II

Advanced

  • Permutation Sequence (the k-th permutation)
  • Beautiful Arrangement

Key takeaways

  • Subsets and combinations loop forward from a start index; permutations loop over all unused indices.
  • Sort and skip equal neighbours to avoid duplicate results.
  • Result sizes: 2^n subsets, C(n, k) combinations, n! permutations.