Java backtracking: subset choices and restoring state

Java 8+. The program uses only JDK classes and runs without a framework.

The selected list belongs to one branch at a time

A packing station must enumerate combinations of positive package weights that reach a target. At each input position, the search can include that package or skip it. The selected list records the current branch, while the result list retains completed combinations.

The include branch appends a weight and removes that same final element after returning. Without restoration, the skip branch inherits a choice it did not make. Completed solutions copy the selected list, because keeping the same mutable list reference would make later removals rewrite previously found solutions.

Each input position can be used once. Equal weights at different positions remain distinct choices, so this version can return repeated-looking value combinations. If the business asks for unique value combinations, group equal weights or add a deliberate deduplication strategy. Do not erase duplicates after the search without considering its additional memory cost.

Prune only under the stated precondition

The method includes a weight only when it fits the remaining positive target. That pruning depends on strictly positive weights. A negative weight could bring an oversized partial choice back down later, and a zero changes termination and duplicate-result reasoning. The public method rejects both.

A target of zero has one solution: choose no packages. Reaching zero adds the copied branch and stops that branch because additional positive weights cannot preserve the target. An unreachable positive target returns an empty result list. Read recursive progress before adding more pruning conditions.

Working program

import java.util.ArrayList;
import java.util.List;
public class PackingCombinations {
    static void search(int[] weights, int index, int remaining,
                       List<Integer> selected, List<List<Integer>> results) {
        if (remaining == 0) { results.add(new ArrayList<>(selected)); return; }
        if (index == weights.length) return;
        if (weights[index] <= remaining) {
            selected.add(weights[index]);
            search(weights, index + 1, remaining - weights[index], selected, results);
            selected.remove(selected.size() - 1);
        }
        search(weights, index + 1, remaining, selected, results);
    }
    static List<List<Integer>> combinations(int[] weights, int target) {
        if (target < 0) throw new IllegalArgumentException("Negative target");
        for (int weight : weights) if (weight <= 0) throw new IllegalArgumentException("Positive weights required");
        List<List<Integer>> results = new ArrayList<>();
        search(weights, 0, target, new ArrayList<>(), results);
        return results;
    }
    public static void main(String[] args) {
        System.out.println(combinations(new int[]{2, 3, 5, 7}, 10));
        System.out.println(combinations(new int[]{4, 6}, 0));
    }
}

Output

[[2, 3, 5], [3, 7]]
[[]]

Cost and failure boundaries

The include/skip tree has up to O(2^n) search nodes for n packages. Copying r solutions can add O(nr) output work and storage. The call stack and mutable branch use O(n) working space. Pruning helps particular inputs, but does not establish a polynomial worst-case bound.

If the caller needs only whether a combination exists, enumerating every solution wastes work and memory. A boolean search can stop at the first result, or a cached-state method can reuse repeated index/remaining subproblems. The memoization lesson discusses the changed state and space trade-off.

Common Mistakes

• Restore branch state before exploring a sibling branch.
• Copy a found solution before retaining it.
• Do not use positive-weight pruning on an input model that allows negative values.

Connect the contracts

Compare the boundary explained in Pair search instead of arbitrary subsets with the assumptions made by this program.