20.04Intermediate5 topics17 min5 interactive animations

Partitioning and sum problems

Sum and partition searches: combination sum, subset sum enumeration, equal-sum partitions, k-partition and matchsticks to a square.

Learning goals

Find all combinations that reach a target, with and without reuse
Split values into k groups of equal sum
Prune with sorted order and overflow tests

Prerequisites

Subset and permutation generation

20.04.1

Combination sum

Find all combinations of candidates that add up to a target, where each candidate may be used any number of times. Sort the candidates, loop from a start index, and recurse with the **same** index (i, not i + 1) because a value may be reused. Stop the loop as soon as sum + a[i] exceeds the target: the candidates are sorted, so every later one overshoots too.

With candidates {2, 3, 5} and target 8 the answers are [2, 2, 2, 2], [2, 3, 3] and [3, 5]. Run the “Combination sum” preset and watch the ✗ nodes where the next candidate overshoots.

Java

1static List<List<Integer>> combinationSum(int[] candidates, int target) {
2    int[] a = candidates.clone(); Arrays.sort(a);
3    List<List<Integer>> out = new ArrayList<>();
4    sumFrom(a, target, 0, 0, new ArrayList<>(), out);
5    return out;
6}
7private static void sumFrom(int[] a, int target, int start, int sum, List<Integer> path, List<List<Integer>> out) {
8    if (sum == target) { out.add(new ArrayList<>(path)); return; }
9    for (int i = start; i < a.length; i++) {
10        if (sum + a[i] > target) break;                        // sorted: every later value is too big as well
11        path.add(a[i]);
12        sumFrom(a, target, i, sum + a[i], path, out);          // i, not i + 1: the same value may be reused
13        path.remove(path.size() - 1);
14    }
15}

Combination sum and subset sum

Interactive · edit the input

partial solution

[] sum 0

solutions found (0)

none yet

Setup

Find combinations that add up to 8. The candidates are sorted, so as soon as one overshoots the target, all later ones do too and the loop stops (pruning). A value may be chosen again, so the recursion restarts at the same index.

Step 1 / 49

Java

1static void sum(int[] a, int target, int start, int sum, List<Integer> path, List<List<Integer>> out, boolean reuse) {   // a sorted, positive
2    if (sum == target) { out.add(new ArrayList<>(path)); return; }
3    for (int i = start; i < a.length; i++) {
4        if (sum + a[i] > target) break;                           // sorted: every later value is too big as well
5        path.add(a[i]);                                          // choose
6        sum(a, target, reuse ? i : i + 1, sum + a[i], path, out, reuse);   // explore (reuse: i again; else: next value)
7        path.remove(path.size() - 1);                            // unchoose
8    }
9}

Live state

depth

solutions

No condition evaluated on this step

Call stack (top first)

empty

Execution trace (dry run table)Show 49 steps

Step	Line	State	What happens
1	L1	depth=0 solutions=0	Find combinations that add up to 8. The candidates are sorted, so as soon as one overshoots the target, all later ones do too and the loop stops (pruning). A value may be chosen again, so the recursion restarts at the same index.
2	L1	depth=1 solutions=0	Explore [] sum 0.
3	L5	depth=1 solutions=0	Choose 2.
4	L1	depth=2 solutions=0	Explore [2] sum 2.
5	L5	depth=2 solutions=0	Choose 2.
6	L1	depth=3 solutions=0	Explore [2, 2] sum 4.
7	L5	depth=3 solutions=0	Choose 2.
8	L1	depth=4 solutions=0	Explore [2, 2, 2] sum 6.
9	L5	depth=4 solutions=0	Choose 2.
10	L1	depth=5 solutions=0	Explore [2, 2, 2, 2] sum 8.
11	L2	depth=5 solutions=1	Complete and valid: record [2, 2, 2, 2].
12	L7	depth=4 solutions=1	Unchoose 2: back to [2, 2, 2] sum 6.
13	L4	depth=5 solutions=1	Reject 3: 6 + 3 = 9 is above 8, and the sorted candidates after it are larger still.
14	L7	depth=3 solutions=1	Unchoose 2: back to [2, 2] sum 4.
15	L5	depth=3 solutions=1	Choose 3.
16	L1	depth=4 solutions=1	Explore [2, 2, 3] sum 7.
17	L4	depth=5 solutions=1	Reject 3: 7 + 3 = 10 is above 8, and the sorted candidates after it are larger still.
18	L7	depth=3 solutions=1	Unchoose 3: back to [2, 2] sum 4.
19	L4	depth=4 solutions=1	Reject 5: 4 + 5 = 9 is above 8, and the sorted candidates after it are larger still.
20	L7	depth=2 solutions=1	Unchoose 2: back to [2] sum 2.
21	L5	depth=2 solutions=1	Choose 3.
22	L1	depth=3 solutions=1	Explore [2, 3] sum 5.
23	L5	depth=3 solutions=1	Choose 3.
24	L1	depth=4 solutions=1	Explore [2, 3, 3] sum 8.
25	L2	depth=4 solutions=2	Complete and valid: record [2, 3, 3].
26	L7	depth=3 solutions=2	Unchoose 3: back to [2, 3] sum 5.
27	L4	depth=4 solutions=2	Reject 5: 5 + 5 = 10 is above 8, and the sorted candidates after it are larger still.
28	L7	depth=2 solutions=2	Unchoose 3: back to [2] sum 2.
29	L5	depth=2 solutions=2	Choose 5.
30	L1	depth=3 solutions=2	Explore [2, 5] sum 7.
31	L4	depth=4 solutions=2	Reject 5: 7 + 5 = 12 is above 8, and the sorted candidates after it are larger still.
32	L7	depth=2 solutions=2	Unchoose 5: back to [2] sum 2.
33	L7	depth=1 solutions=2	Unchoose 2: back to [] sum 0.
34	L5	depth=1 solutions=2	Choose 3.
35	L1	depth=2 solutions=2	Explore [3] sum 3.
36	L5	depth=2 solutions=2	Choose 3.
37	L1	depth=3 solutions=2	Explore [3, 3] sum 6.
38	L4	depth=4 solutions=2	Reject 3: 6 + 3 = 9 is above 8, and the sorted candidates after it are larger still.
39	L7	depth=2 solutions=2	Unchoose 3: back to [3] sum 3.
40	L5	depth=2 solutions=2	Choose 5.
41	L1	depth=3 solutions=2	Explore [3, 5] sum 8.
42	L2	depth=3 solutions=3	Complete and valid: record [3, 5].
43	L7	depth=2 solutions=3	Unchoose 5: back to [3] sum 3.
44	L7	depth=1 solutions=3	Unchoose 3: back to [] sum 0.
45	L5	depth=1 solutions=3	Choose 5.
46	L1	depth=2 solutions=3	Explore [5] sum 5.
47	L4	depth=3 solutions=3	Reject 5: 5 + 5 = 10 is above 8, and the sorted candidates after it are larger still.
48	L7	depth=1 solutions=3	Unchoose 5: back to [] sum 0.
49	L9	solutions=3 nodes=20 return=[[2, 2, 2, 2], [2, 3, 3], [3, 5]]	Search finished: 3 solutions, 19 choices tried. Backtracking explores every branch the pruning rules allow.

20.04.2

Subset sum enumeration

The same search with each value usable **once** enumerates the subsets whose sum is the target: recurse with i + 1. This is the exact, exponential version of the subset sum problem; Chapter 23 solves the *decision* version with dynamic programming in O(n · target) time, which is much faster when the target is small. Backtracking is the right tool when you need the actual subsets, not only whether one exists.

The “Subset sum” preset finds [2, 3, 4] and [4, 5] for target 9 from {2, 3, 4, 5}. “No solution” explores and rejects every branch for {4, 6} and target 7.

Java

1static List<List<Integer>> subsetSums(int[] values, int target) {      // positive values, each used at most once
2    int[] a = values.clone(); Arrays.sort(a);
3    List<List<Integer>> out = new ArrayList<>();
4    take(a, target, 0, 0, new ArrayList<>(), out);
5    return out;
6}
7private static void take(int[] a, int target, int start, int sum, List<Integer> path, List<List<Integer>> out) {
8    if (sum == target) { out.add(new ArrayList<>(path)); return; }
9    for (int i = start; i < a.length; i++) {
10        if (sum + a[i] > target) break;
11        path.add(a[i]);
12        take(a, target, i + 1, sum + a[i], path, out);         // i + 1: each value at most once
13        path.remove(path.size() - 1);
14    }
15}

Combination sum and subset sum

Interactive · edit the input

partial solution

[] sum 0

solutions found (0)

none yet

Setup

Step 1 / 49

Java

1static void sum(int[] a, int target, int start, int sum, List<Integer> path, List<List<Integer>> out, boolean reuse) {   // a sorted, positive
2    if (sum == target) { out.add(new ArrayList<>(path)); return; }
3    for (int i = start; i < a.length; i++) {
4        if (sum + a[i] > target) break;                           // sorted: every later value is too big as well
5        path.add(a[i]);                                          // choose
6        sum(a, target, reuse ? i : i + 1, sum + a[i], path, out, reuse);   // explore (reuse: i again; else: next value)
7        path.remove(path.size() - 1);                            // unchoose
8    }
9}

Live state

depth

solutions

No condition evaluated on this step

Call stack (top first)

empty

Execution trace (dry run table)Show 49 steps

Step	Line	State	What happens
1	L1	depth=0 solutions=0	Find combinations that add up to 8. The candidates are sorted, so as soon as one overshoots the target, all later ones do too and the loop stops (pruning). A value may be chosen again, so the recursion restarts at the same index.
2	L1	depth=1 solutions=0	Explore [] sum 0.
3	L5	depth=1 solutions=0	Choose 2.
4	L1	depth=2 solutions=0	Explore [2] sum 2.
5	L5	depth=2 solutions=0	Choose 2.
6	L1	depth=3 solutions=0	Explore [2, 2] sum 4.
7	L5	depth=3 solutions=0	Choose 2.
8	L1	depth=4 solutions=0	Explore [2, 2, 2] sum 6.
9	L5	depth=4 solutions=0	Choose 2.
10	L1	depth=5 solutions=0	Explore [2, 2, 2, 2] sum 8.
11	L2	depth=5 solutions=1	Complete and valid: record [2, 2, 2, 2].
12	L7	depth=4 solutions=1	Unchoose 2: back to [2, 2, 2] sum 6.
13	L4	depth=5 solutions=1	Reject 3: 6 + 3 = 9 is above 8, and the sorted candidates after it are larger still.
14	L7	depth=3 solutions=1	Unchoose 2: back to [2, 2] sum 4.
15	L5	depth=3 solutions=1	Choose 3.
16	L1	depth=4 solutions=1	Explore [2, 2, 3] sum 7.
17	L4	depth=5 solutions=1	Reject 3: 7 + 3 = 10 is above 8, and the sorted candidates after it are larger still.
18	L7	depth=3 solutions=1	Unchoose 3: back to [2, 2] sum 4.
19	L4	depth=4 solutions=1	Reject 5: 4 + 5 = 9 is above 8, and the sorted candidates after it are larger still.
20	L7	depth=2 solutions=1	Unchoose 2: back to [2] sum 2.
21	L5	depth=2 solutions=1	Choose 3.
22	L1	depth=3 solutions=1	Explore [2, 3] sum 5.
23	L5	depth=3 solutions=1	Choose 3.
24	L1	depth=4 solutions=1	Explore [2, 3, 3] sum 8.
25	L2	depth=4 solutions=2	Complete and valid: record [2, 3, 3].
26	L7	depth=3 solutions=2	Unchoose 3: back to [2, 3] sum 5.
27	L4	depth=4 solutions=2	Reject 5: 5 + 5 = 10 is above 8, and the sorted candidates after it are larger still.
28	L7	depth=2 solutions=2	Unchoose 3: back to [2] sum 2.
29	L5	depth=2 solutions=2	Choose 5.
30	L1	depth=3 solutions=2	Explore [2, 5] sum 7.
31	L4	depth=4 solutions=2	Reject 5: 7 + 5 = 12 is above 8, and the sorted candidates after it are larger still.
32	L7	depth=2 solutions=2	Unchoose 5: back to [2] sum 2.
33	L7	depth=1 solutions=2	Unchoose 2: back to [] sum 0.
34	L5	depth=1 solutions=2	Choose 3.
35	L1	depth=2 solutions=2	Explore [3] sum 3.
36	L5	depth=2 solutions=2	Choose 3.
37	L1	depth=3 solutions=2	Explore [3, 3] sum 6.
38	L4	depth=4 solutions=2	Reject 3: 6 + 3 = 9 is above 8, and the sorted candidates after it are larger still.
39	L7	depth=2 solutions=2	Unchoose 3: back to [3] sum 3.
40	L5	depth=2 solutions=2	Choose 5.
41	L1	depth=3 solutions=2	Explore [3, 5] sum 8.
42	L2	depth=3 solutions=3	Complete and valid: record [3, 5].
43	L7	depth=2 solutions=3	Unchoose 5: back to [3] sum 3.
44	L7	depth=1 solutions=3	Unchoose 3: back to [] sum 0.
45	L5	depth=1 solutions=3	Choose 5.
46	L1	depth=2 solutions=3	Explore [5] sum 5.
47	L4	depth=3 solutions=3	Reject 5: 5 + 5 = 10 is above 8, and the sorted candidates after it are larger still.
48	L7	depth=1 solutions=3	Unchoose 5: back to [] sum 0.
49	L9	solutions=3 nodes=20 return=[[2, 2, 2, 2], [2, 3, 3], [3, 5]]	Search finished: 3 solutions, 19 choices tried. Backtracking explores every branch the pruning rules allow.

20.04.3

Equal-sum partitions

Can an array be split into two groups with the same sum? The total must be even; the target for each group is half. That is a subset sum question (is there a subset with sum total/2?). For k = 2 the partition search below works, and the dynamic-programming solution of Chapter 23 is faster for large values. In the animation the “Equal halves” preset splits [1, 5, 11, 5] into two groups of 11.

Java

1static boolean canSplitEqually(int[] a) {
2    int total = Arrays.stream(a).sum();
3    if (total % 2 != 0) return false;                          // an odd total cannot be halved
4    int[] sorted = a.clone(); Arrays.sort(sorted);
5    return reach(sorted, sorted.length - 1, total / 2);
6}
7private static boolean reach(int[] a, int i, int remaining) {  // can a[0..i] make exactly `remaining`?
8    if (remaining == 0) return true;
9    if (i < 0 || remaining < 0) return false;
10    return reach(a, i - 1, remaining - a[i]) || reach(a, i - 1, remaining);   // take a[i], or skip it
11}

Partition into k equal-sum groups (equal partitions, matchsticks)

Interactive · edit the input

partial solution

sums [0, 0, 0]

solutions found (0)

none yet

goal 6 per group

0/6G1

0/6G2

0/6G3

Setup

Total 18 split into 3 groups: each group must reach 6. Values are placed largest first so overflowing branches fail early.

Step 1 / 22

Java

1static boolean canPartition(int[] a, int k, boolean symmetry) {       // a sorted in descending order
2    int total = Arrays.stream(a).sum();
3    if (total % k != 0 || a[0] > total / k) return false;
4    return place(a, 0, new int[k], total / k, symmetry);
5}
6static boolean place(int[] a, int i, int[] sums, int goal, boolean symmetry) {
7    if (i == a.length) return true;                                   // everything placed
8    for (int b = 0; b < sums.length; b++) {
9        if (sums[b] + a[i] > goal) continue;                          // this group would overflow
10        if (symmetry && b > 0 && sums[b] == 0 && sums[b - 1] == 0) break;   // identical empty groups: try only the first
11        sums[b] += a[i];                                              // choose
12        if (place(a, i + 1, sums, goal, symmetry)) return true;       // explore
13        sums[b] -= a[i];                                              // unchoose
14    }
15    return false;
16}

Live state

depth

solutions

No condition evaluated on this step

Call stack (top first)

empty

Execution trace (dry run table)Show 22 steps

Step	Line	State	What happens
1	L4	depth=0 solutions=0	Total 18 split into 3 groups: each group must reach 6. Values are placed largest first so overflowing branches fail early.
2	L6	depth=1 solutions=0	Explore sums [0, 0, 0].
3	L11	depth=1 solutions=0	Choose 4→G1.
4	L6	depth=2 solutions=0	Explore sums [4, 0, 0].
5	L9	depth=3 solutions=0	Reject 4→G1: group 1 would reach 8, above 6.
6	L11	depth=2 solutions=0	Choose 4→G2.
7	L6	depth=3 solutions=0	Explore sums [4, 4, 0].
8	L9	depth=4 solutions=0	Reject 3→G1: group 1 would reach 7, above 6.
9	L9	depth=4 solutions=0	Reject 3→G2: group 2 would reach 7, above 6.
10	L11	depth=3 solutions=0	Choose 3→G3.
11	L6	depth=4 solutions=0	Explore sums [4, 4, 3].
12	L9	depth=5 solutions=0	Reject 3→G1: group 1 would reach 7, above 6.
13	L9	depth=5 solutions=0	Reject 3→G2: group 2 would reach 7, above 6.
14	L11	depth=4 solutions=0	Choose 3→G3.
15	L6	depth=5 solutions=0	Explore sums [4, 4, 6].
16	L11	depth=5 solutions=0	Choose 2→G1.
17	L6	depth=6 solutions=0	Explore sums [6, 4, 6].
18	L9	depth=7 solutions=0	Reject 2→G1: group 1 would reach 8, above 6.
19	L11	depth=6 solutions=0	Choose 2→G2.
20	L6	depth=7 solutions=0	Explore sums [6, 6, 6].
21	L7	depth=7 solutions=1	Complete and valid: record [4→G1, 4→G2, 3→G3, 3→G3, 2→G1, 2→G2].
22	L15	solutions=1 nodes=13 return=true	Search finished: 1 solution, 12 choices tried. Backtracking explores every branch the pruning rules allow.

20.04.4

K-partition

Split the values into k groups that all have the same sum. The total must be divisible by k and no value may exceed the target sum total/k. Then place the values one at a time into one of the k groups, rejecting a placement that would push a group above the target. Sorting the values in descending order makes overflow happen early, and the animation's auxiliary row shows each group's running sum against the goal.

Two cheap checks avoid whole searches: a non-divisible total is rejected before any recursion, and a value larger than the goal means failure. For [4, 4, 4, 3, 3] and k = 3 the total 18 is divisible, the goal is 6, but no placement exists; the search needs only 12 nodes with symmetry breaking (see the search-improvements lesson) and 49 without.

Java

1static boolean canPartition(int[] a, int k) {                 // a sorted in descending order
2    int total = Arrays.stream(a).sum();
3    if (total % k != 0 || a[0] > total / k) return false;
4    return place(a, 0, new int[k], total / k);
5}
6private static boolean place(int[] a, int i, int[] sums, int goal) {
7    if (i == a.length) return true;                           // everything placed
8    for (int b = 0; b < sums.length; b++) {
9        if (sums[b] + a[i] > goal) continue;                  // this group would overflow
10        sums[b] += a[i];                                      // choose
11        if (place(a, i + 1, sums, goal)) return true;         // explore
12        sums[b] -= a[i];                                      // unchoose
13    }
14    return false;
15}

Partition into k equal-sum groups (equal partitions, matchsticks)

Interactive · edit the input

partial solution

sums [0, 0, 0]

solutions found (0)

none yet

goal 6 per group

0/6G1

0/6G2

0/6G3

Setup

Total 18 split into 3 groups: each group must reach 6. Values are placed largest first so overflowing branches fail early.

Step 1 / 22

Java

1static boolean canPartition(int[] a, int k, boolean symmetry) {       // a sorted in descending order
2    int total = Arrays.stream(a).sum();
3    if (total % k != 0 || a[0] > total / k) return false;
4    return place(a, 0, new int[k], total / k, symmetry);
5}
6static boolean place(int[] a, int i, int[] sums, int goal, boolean symmetry) {
7    if (i == a.length) return true;                                   // everything placed
8    for (int b = 0; b < sums.length; b++) {
9        if (sums[b] + a[i] > goal) continue;                          // this group would overflow
10        if (symmetry && b > 0 && sums[b] == 0 && sums[b - 1] == 0) break;   // identical empty groups: try only the first
11        sums[b] += a[i];                                              // choose
12        if (place(a, i + 1, sums, goal, symmetry)) return true;       // explore
13        sums[b] -= a[i];                                              // unchoose
14    }
15    return false;
16}

Live state

depth

solutions

No condition evaluated on this step

Call stack (top first)

empty

Execution trace (dry run table)Show 22 steps

Step	Line	State	What happens
1	L4	depth=0 solutions=0	Total 18 split into 3 groups: each group must reach 6. Values are placed largest first so overflowing branches fail early.
2	L6	depth=1 solutions=0	Explore sums [0, 0, 0].
3	L11	depth=1 solutions=0	Choose 4→G1.
4	L6	depth=2 solutions=0	Explore sums [4, 0, 0].
5	L9	depth=3 solutions=0	Reject 4→G1: group 1 would reach 8, above 6.
6	L11	depth=2 solutions=0	Choose 4→G2.
7	L6	depth=3 solutions=0	Explore sums [4, 4, 0].
8	L9	depth=4 solutions=0	Reject 3→G1: group 1 would reach 7, above 6.
9	L9	depth=4 solutions=0	Reject 3→G2: group 2 would reach 7, above 6.
10	L11	depth=3 solutions=0	Choose 3→G3.
11	L6	depth=4 solutions=0	Explore sums [4, 4, 3].
12	L9	depth=5 solutions=0	Reject 3→G1: group 1 would reach 7, above 6.
13	L9	depth=5 solutions=0	Reject 3→G2: group 2 would reach 7, above 6.
14	L11	depth=4 solutions=0	Choose 3→G3.
15	L6	depth=5 solutions=0	Explore sums [4, 4, 6].
16	L11	depth=5 solutions=0	Choose 2→G1.
17	L6	depth=6 solutions=0	Explore sums [6, 4, 6].
18	L9	depth=7 solutions=0	Reject 2→G1: group 1 would reach 8, above 6.
19	L11	depth=6 solutions=0	Choose 2→G2.
20	L6	depth=7 solutions=0	Explore sums [6, 6, 6].
21	L7	depth=7 solutions=1	Complete and valid: record [4→G1, 4→G2, 3→G3, 3→G3, 2→G1, 2→G2].
22	L15	solutions=1 nodes=13 return=true	Search finished: 1 solution, 12 choices tried. Backtracking explores every branch the pruning rules allow.

20.04.5

Matchsticks to square

Can all the matchsticks be arranged into the four sides of a square, using every stick exactly once? That is k-partition with k = 4: the sides must all have length total/4. The checks are the same: total divisible by 4, no stick longer than a side. Sort sticks in descending order so long sticks are placed first.

The “Matchsticks to a square” preset uses sticks [1, 1, 2, 2, 2] and finds the sides {2}, {2}, {2}, {1, 1} after 15 nodes: the total is 8, so every side is 2.

Java

1static boolean makesSquare(int[] sticks) {
2    int[] a = sticks.clone(); Arrays.sort(a);
3    for (int i = 0, j = a.length - 1; i < j; i++, j--) { int t = a[i]; a[i] = a[j]; a[j] = t; }   // descending
4    if (a.length < 4) return false;
5    int total = Arrays.stream(a).sum();
6    if (total % 4 != 0 || a[0] > total / 4) return false;
7    return fill(a, 0, new int[4], total / 4);
8}
9private static boolean fill(int[] a, int i, int[] sides, int goal) {
10    if (i == a.length) return true;
11    for (int s = 0; s < 4; s++) {
12        if (sides[s] + a[i] > goal) continue;
13        sides[s] += a[i];
14        if (fill(a, i + 1, sides, goal)) return true;
15        sides[s] -= a[i];
16    }
17    return false;
18}

Partition into k equal-sum groups (equal partitions, matchsticks)

Interactive · edit the input

partial solution

sums [0, 0, 0]

solutions found (0)

none yet

goal 6 per group

0/6G1

0/6G2

0/6G3

Setup

Total 18 split into 3 groups: each group must reach 6. Values are placed largest first so overflowing branches fail early.

Step 1 / 22

Java

1static boolean canPartition(int[] a, int k, boolean symmetry) {       // a sorted in descending order
2    int total = Arrays.stream(a).sum();
3    if (total % k != 0 || a[0] > total / k) return false;
4    return place(a, 0, new int[k], total / k, symmetry);
5}
6static boolean place(int[] a, int i, int[] sums, int goal, boolean symmetry) {
7    if (i == a.length) return true;                                   // everything placed
8    for (int b = 0; b < sums.length; b++) {
9        if (sums[b] + a[i] > goal) continue;                          // this group would overflow
10        if (symmetry && b > 0 && sums[b] == 0 && sums[b - 1] == 0) break;   // identical empty groups: try only the first
11        sums[b] += a[i];                                              // choose
12        if (place(a, i + 1, sums, goal, symmetry)) return true;       // explore
13        sums[b] -= a[i];                                              // unchoose
14    }
15    return false;
16}

Live state

depth

solutions

No condition evaluated on this step

Call stack (top first)

empty

Execution trace (dry run table)Show 22 steps

Step	Line	State	What happens
1	L4	depth=0 solutions=0	Total 18 split into 3 groups: each group must reach 6. Values are placed largest first so overflowing branches fail early.
2	L6	depth=1 solutions=0	Explore sums [0, 0, 0].
3	L11	depth=1 solutions=0	Choose 4→G1.
4	L6	depth=2 solutions=0	Explore sums [4, 0, 0].
5	L9	depth=3 solutions=0	Reject 4→G1: group 1 would reach 8, above 6.
6	L11	depth=2 solutions=0	Choose 4→G2.
7	L6	depth=3 solutions=0	Explore sums [4, 4, 0].
8	L9	depth=4 solutions=0	Reject 3→G1: group 1 would reach 7, above 6.
9	L9	depth=4 solutions=0	Reject 3→G2: group 2 would reach 7, above 6.
10	L11	depth=3 solutions=0	Choose 3→G3.
11	L6	depth=4 solutions=0	Explore sums [4, 4, 3].
12	L9	depth=5 solutions=0	Reject 3→G1: group 1 would reach 7, above 6.
13	L9	depth=5 solutions=0	Reject 3→G2: group 2 would reach 7, above 6.
14	L11	depth=4 solutions=0	Choose 3→G3.
15	L6	depth=5 solutions=0	Explore sums [4, 4, 6].
16	L11	depth=5 solutions=0	Choose 2→G1.
17	L6	depth=6 solutions=0	Explore sums [6, 4, 6].
18	L9	depth=7 solutions=0	Reject 2→G1: group 1 would reach 8, above 6.
19	L11	depth=6 solutions=0	Choose 2→G2.
20	L6	depth=7 solutions=0	Explore sums [6, 6, 6].
21	L7	depth=7 solutions=1	Complete and valid: record [4→G1, 4→G2, 3→G3, 3→G3, 2→G1, 2→G2].
22	L15	solutions=1 nodes=13 return=true	Search finished: 1 solution, 12 choices tried. Backtracking explores every branch the pruning rules allow.

Practice ladder

Now try it yourself

Easy

Combination Sum (target 7, candidates 2, 3, 6, 7)
Subsets

Medium

Combination Sum II
Partition Equal Subset Sum
Matchsticks to Square

Advanced

Partition to K Equal Sum Subsets
Target Sum

Key takeaways

Sort candidates, restart at i to allow reuse, at i + 1 to forbid it, and break when the sum overshoots.
k-partition needs total % k == 0 and max ≤ total/k before any search.
Backtracking gives the actual groups; dynamic programming (Chapter 23) answers existence faster.