Backtracking and Pruned Search

Consider selecting some entries from a list of non-negative integers so their sum equals a target. At each position, choose to include that entry or skip it. A path records the chosen entries, and moving to the next position prevents using the same entry repeatedly. The order of choices determines which valid solution is found first.

Backtracking returns to an earlier decision when a branch cannot succeed. If path is mutable, undo an appended choice before trying the alternative branch. Otherwise a value from a failed path can leak into a later candidate. Returning a copy of a successful path also separates the result from subsequent changes to the search state.

For non-negative inputs, a partial total larger than the target can never be reduced by adding remaining entries, so that branch can be pruned. Negative entries would invalidate this rule: a later negative value might bring the total down. The example therefore rejects negative numbers and negative targets rather than silently applying an unsound optimisation.

A total equal to the target succeeds, including an empty subset for target zero. If all positions have been considered without success, return no solution. The index increases on every recursive step, giving a finite search tree. Repeated equal values can still be distinct entries; state whether the task wants any solution, all index-distinct solutions or unique value combinations.

Without effective pruning, n independent include/skip decisions create up to 2ⁿ subsets. Backtracking can be useful for constraint satisfaction, puzzles and search through possible assignments, but it is not automatically an efficient solution for large inputs. The quality of constraints and the order of choices can strongly affect practical exploration.

The example returns one solution and stops; it does not establish uniqueness or optimality. Trace both a successful and unsuccessful input. Test zero, an empty list, repeated values and cases where the first branch fails. A clear explanation connects each rejected branch to a rule, rather than saying the computer simply tries random answers.

def subset_sum(numbers, target):
    if target < 0 or any(value < 0 for value in numbers):
        raise ValueError("non-negative values required")
    path = []
    def search(index, total):
        if total == target:
            return path.copy()
        if total > target or index == len(numbers):
            return None
        path.append(numbers[index])
        result = search(index + 1, total + numbers[index])
        path.pop()
        if result is not None:
            return result
        return search(index + 1, total)
    return search(0, 0)

print(subset_sum([3, 5, 7], 8))
print(subset_sum([3, 5, 7], 9))

Attempt the task before opening its worked response. Record each change of state, explain the rule used, and check the result against the original requirements. Code examples labelled Python 3 use that language’s conventions; pseudocode states its own assumptions.