Lesson 16 · 16 of 20

Recursion and backtracking · Pascal

Solve search problems with recursion and backtracking in Pascal: which pending invoices add up exactly to the amount of a payment.

Pascal · Recursion and backtracking in DMarlon Studio: the example's code and its output in the terminal

A customer pays 500 EUR and there are six pending invoices: which combinations add up to exactly that amount? It is a real bank reconciliation task and a perfect example of backtracking: try an option, keep exploring and, if it leads nowhere, undo it and try the next one.

Search(i, remaining) decides about invoice i knowing how much is still to be covered. It has two base cases, the ones that stop the recursion: if remaining reaches 0, the current selection is a solution and gets printed; if the invoices run out or the amount overshoots (goes negative), that path is a dead end and Exit goes back.

The heart of it is the last four lines: choose the invoice (chosen[i] := True) and explore the rest with what is left; then undo the choice (chosen[i] := False) and explore the rest without it. That covers every combination, 2⁶ = 64 at most, and drops the ones that overshoot early.

The chosen array is the shared state that gets marked and unmarked, and found counts the solutions; Free Pascal lets you initialise a global variable in its declaration, as in found: Integer = 0. The result: four different ways to match the payment.

Code · main.pas

program main;const  Invoices: array[0..5] of Integer = (120, 340, 90, 160, 250, 40);  Payment = 500;var  chosen: array[0..5] of Boolean;  found: Integer = 0;procedure Search(i, remaining: Integer);var k: Integer;begin  if remaining = 0 then  // a match: print the chosen invoices  begin    Inc(found);    Write('Option ', found, ':');    for k := 0 to High(Invoices) do      if chosen[k] then Write(' ', Invoices[k]);    WriteLn;    Exit;  end;  if (i > High(Invoices)) or (remaining < 0) then Exit;  // dead end: go back  chosen[i] := True;             // try with invoice i...  Search(i + 1, remaining - Invoices[i]);  chosen[i] := False;            // ...undo, and try without it  Search(i + 1, remaining);end;begin  Search(0, Payment);  WriteLn(found, ' ways to match a payment of ', Payment);end.

Output · fpc main.pas && ./main

Option 1: 120 340 40
Option 2: 120 90 250 40
Option 3: 340 160
Option 4: 90 160 250
4 ways to match a payment of 500

Key points

A recursive function calls itself with a smaller problem.
Base cases stop the recursion.
Backtracking: choose, explore, undo.
Pruning impossible paths early saves work.
Shared state is marked before and unmarked after.

Exercise

Make the search stop as soon as it finds the first combination and print the invoices' positions in the array instead of their amounts.