DSA Backtracking

How it works

The fixture chooses each nonnegative observation at most once to reach an exact target. An index identifies the chosen record, so repeated equal values remain distinct available positions. A negative remaining target can be abandoned only because later values are nonnegative. The zero target accepts the empty subset. This returns one witness, not every possible subset or a minimum-cardinality solution.

Run the code

Select Try in playground to load this complete source into the existing Python editor. It does not run automatically; choose Run when ready. These examples use only the Python standard library and small fictional inputs. They do not need database services, extra packages or personal files.

For local work, save the complete source as backtracking.py and run python backtracking.py. The local review uses Python 3.12.14; the browser uses the existing Pyodide 0.27.7 runtime. Keep inputs small, respect explicit table/tour budgets and account for recursion limits before increasing a fixture’s size.

Example

def subset_sum(values, target):
    if type(target) is not int or target < 0 or any(type(value) is not int or value < 0 for value in values):
        raise ValueError("Nonnegative integer inputs required")

    def choose(index, remaining):
        if remaining == 0:
            return []
        if index == len(values) or remaining < 0:
            return None
        included = choose(index + 1, remaining - values[index])
        if included is not None:
            return [index] + included
        return choose(index + 1, remaining)

    return choose(0, target)

values = [7, 4, 6]
chosen = subset_sum(values, 11)
print(chosen)
print(sum(values[index] for index in chosen))
print(subset_sum([4, 6], 3))

Expected result

[0, 1]
11
None

The first two positions reach eleven and the separate impossible target returns None. The returned indexes can be checked for uniqueness and range. The property review compares existence with exhaustive bit masks on short inputs, including zeros and repeated values.

Time, space and assumptions

The choice tree is exponential. A conservative O(n·2^n) bound includes witness-list construction; recursion and a returned witness use O(n) peak storage for the small bounded fixtures.