Community resourceWorksheet

OCR H446 2.2.2 Writing backtracking algorithms

Part 5 of 14 · H446 2.2.2 · Computational methods

Reading a backtracking template is far easier than writing one that terminates and restores its state correctly. This H446 2.2.2 worksheet moves students from the template to their own subset-sum implementation, by way of a debugging task built around the classic missing undo after a failed recursive call.

Students will:

  • define the state, the alternatives, the success test and the failure test for a backtracking problem
  • explain when a running total exceeding the target is a safe failure test
  • diagnose how a missing undo step corrupts a later route or the returned path
  • implement a subset-sum search that uses each value at most once and leaves the input list unchanged
  • explain why the order of the include and exclude routes changes running time but not the set of solutions reachable

Inside: 7 explanation cells, 1 multiple-choice question, 1 fill-in-the-blanks cell, 2 written answers and 1 Python task. 22 marks, about 25 to 40 minutes.

Series: H446 2.2.2 · Computational methods, part 5 of 14.

Shared by Coding PathwayVerified teacher

  • 12 cells
  • About 30 minutes
  • CC BY-SA 4.0
  • Shared 31 Aug 2026
  • Updated 3 Sept 2026

Preview

The whole resource, exactly as a class sees it. Answers and marking are held back.

Writing backtracking algorithms

A set of workshop durations must be combined to fill an available time exactly. This worksheet moves from reading a backtracking template to implementing and debugging one.

By the end, you will be able to

  • define the state and alternatives in a backtracking problem;
  • write success, failure and progress cases;
  • restore mutable state correctly;
  • test a search with solutions, dead ends and boundaries.

Reactivate: every recursive route must reach a base case.

A state-preserving template

search(partial state):
    if partial state is a solution: return success
    if partial state cannot lead to a solution: return failure
    for each remaining choice:
        apply choice
        if search(updated state) succeeds: return success
        undo choice
    return failure

The success test recognises a complete answer. The failure test prunes impossible routes. Applying and undoing must be symmetric when state is changed in place. An implementation that passes copied state may restore it implicitly, but the logical backtracking step is still present when a failed call returns and another choice is tried.

Worked design: exact duration

State can be represented by index and total. At each index there are two alternatives: include the duration or exclude it.

  • success: total == target;
  • failure: index == len(values) before success, or total > target when every value is non-negative;
  • progress: both routes increase index;
  • alternatives: include first, then exclude if it fails.

The total > target pruning rule would be unsafe if negative durations were allowed. A pruning condition is justified by the stated data constraints.

Multiple choice1 mark

When is total > target a safe failure test for subset sum?

  • AWhen all remaining values are non-negative
  • BWhenever the list is sorted
  • COnly when recursion is not used
  • DWhenever the target is even

Guided debugging: the missing undo

A path search executes path.append(room) before a recursive call. If the call fails, it immediately tries another room without removing the previous one. The second route now contains a room chosen only on the failed route. Add path.pop() after the failed call and before trying the next alternative.

State-leak symptom → unrelated branches contain old choices. Repair → undo exactly the change made before recursion.

Written answer3 marks

Explain why the missing pop can make a correct route appear invalid or produce an incorrect returned path.

Trace what the next alternative sees in the shared list.

Students type their answer here.

Independent implementation

Implement subset_sum(values, target) for non-negative integers. Return True if some values, each used at most once, total the target. Return False otherwise. Do not alter values.

Coding task10 marks
def subset_sum(values, target):
    # Use a recursive search with include and exclude alternatives.
    pass
Written answer4 marks

The algorithm tries include before exclude. Explain why changing that order may change running time for a particular input but not the set of solutions that can be found.

Distinguish search order from search coverage.

Students type their answer here.

Closed-book checkpoint

Complete each sentence from memory. There is no answer bank and correctness is held for teacher review.

Fill in the blanks4 marks
A backtracking function first needs a checkpoint gap 1 case that recognises a solution and a checkpoint gap 2 case for an exhausted route. A safe early rejection is called checkpoint gap 3. Each recursive route must make finite checkpoint gap 4 towards termination.

Review your understanding

Before submitting, check that you can explain the central distinction in your own words, expose the intermediate state that supports your answer and apply the method in an unfamiliar context.