Introduction

The partitioning problem asks how to split a set of numbers into two groups whose sums are as equal as possible. A recursive backtracking solution explores each choice point explicitly, making it a clear exact algorithm for small inputs and a good teaching example for search and pruning.

Backtracking formulation

For each number, you have two choices:

• put it in the first subset
• put it in the second subset

That creates a binary decision tree. If there are n numbers, a naive exhaustive search can examine up to 2^n assignments.

Backtracking helps structure that search cleanly and gives you a place to prune unpromising branches.

A simple recursive solution

The code below tracks the running sum of one subset. Once all elements are assigned, the other subset sum can be derived from the total.

1from math import inf
2
3
4def partition_min_difference(numbers):
5    total = sum(numbers)
6    best = {"diff": inf, "subset": []}
7
8    def backtrack(index, subset_sum, chosen):
9        if index == len(numbers):
10            other_sum = total - subset_sum
11            diff = abs(subset_sum - other_sum)
12            if diff < best["diff"]:
13                best["diff"] = diff
14                best["subset"] = chosen[:]
15            return
16
17        chosen.append(numbers[index])
18        backtrack(index + 1, subset_sum + numbers[index], chosen)
19        chosen.pop()
20
21        backtrack(index + 1, subset_sum, chosen)
22
23    backtrack(0, 0, [])
24    subset1 = best["subset"]
25    subset2 = numbers[:]
26    for value in subset1:
27        subset2.remove(value)
28
29    return best["diff"], subset1, subset2
30
31
32numbers = [3, 1, 4, 2, 2]
33diff, left, right = partition_min_difference(numbers)
34print(diff, left, right)

This finds an exact best partition by visiting every assignment.

Why this works

At every recursion level, the algorithm makes the complete set of legal choices for the current element. Because no option is skipped, every possible partition is eventually considered.

The algorithm keeps track of the best difference seen so far and replaces it whenever a better partition is found.

That is the essence of recursive backtracking: build a partial solution, recurse, then undo the choice and explore the alternative.

Adding pruning

Backtracking becomes more useful when you add pruning rules that cut off branches that cannot beat the current best result.

For example, if the numbers are sorted and you know the remaining values cannot improve the best known difference, you can stop exploring that branch early. The exact pruning logic depends on the formulation, but even modest pruning can reduce the search noticeably on medium-sized inputs.

A simple improvement is to sort the numbers in descending order first, so large decisions happen earlier and strong bounds appear sooner.

Relationship to dynamic programming

The partition problem also has a dynamic-programming solution based on reachable subset sums. That approach is often better when the total sum is moderate because it avoids the full 2^n search tree.

Backtracking is still valuable when:

• you want the exact subset composition, not just feasibility
• input sizes are small enough that exponential search is acceptable
• you need a clear recursive framework that can be customized with constraints

Complexity

Without pruning, the time complexity is exponential because each element branches into two choices. Space usage is mainly the recursion depth and the storage for the current best solution.

That is why exact backtracking is excellent for small instances and poor for very large ones.

Common Pitfalls

A common mistake is forgetting to undo the current choice before exploring the alternate branch. That breaks the backtracking state and produces incorrect subsets.

Another issue is assuming the algorithm scales well because the code looks short. The search space still grows exponentially.

It is also easy to reconstruct the second subset incorrectly when duplicate numbers exist. If duplicates matter heavily, tracking indexes instead of raw values is safer than removing by value.

Summary

• The partitioning problem can be solved exactly with recursive backtracking.
• Each element creates two branches: one subset or the other.
• The algorithm keeps the best difference found so far and updates it at leaf nodes.
• Sorting and pruning can improve performance, but the worst-case search is still exponential.
• For larger sum-bounded inputs, dynamic programming is often a better exact method.