Backtracking is a method which finds the solution of the problem by testing all possible answers. It is only applied when there is no other way of solving a problem, because its execution time is exponential. The method uses the stack structure and it has an iterative and a recursive way of being implemented.

Problem: We are given n types of coins. From every type of coin k=1..n, we have nr[k] coins of value a[k]. Being given a sum of money p, we are asked to find all the possible ways of paying it with the coins we have.

Solution:

We build a stack st, which has the length n . On every position k of the stack we keep the number of coins of type k that can be paid. Then, we test if the sum of the coins is equal to the sum p. If it is, then we found a solution.

Pascal program:

Iterative version:

var a,st,nr:array[1..100] of integer;
s,max,i,j,k,l,m,n,p:integer;
f:text;
cond:boolean;
begin
assign(f,'in.txt');
reset(f);
read(f,n);
max:=0;
for i:=1 to n do
begin
read(f,a[i],nr[i]);
if a[i]>max then max:=nr[i];
end;
read(f,p);
k:=1; {we start from the first type of coin}
st[k]:=-1;{we initialize the number of coins of that type with -1,
so that by incrementing we can have from 0 to the maximum possible number of coins}
s:=0;{the sum of the value of the coins}
l:=0;{the number of solutions found so far}
repeat
while st[k]<max do
begin
inc(st[k]);
cond:=true;
if st[k]>nr[k] then cond:=false; {if the number of coins taken is bigger than the number of coins given}
if st[k]<>0 then s:=s+a[k];
if s>p then cond:=false;
if cond then if k=n then
begin
if s=p then begin
inc(l);
writeln('Solution ',l);
for i:=1 to n do
if st[i]<>0 then writeln(st[i], ' coins of type ',i);
writeln;
end;
end
else
if k<n then begin
inc(k); {moving to the next type of coins}
st[k]:=-1;
end;
end;
s:=s-st[k]*a[k];
k:=k-1; {going down to the previous type of coins to try another number}
until k=0;
end.

Recursive version:

var st,a,nr:array[1..100] of integer;
i,j,k,l,m,n,,p,s:integer;
f:text;

procedure readdata;
begin
assign(f,'in.txt');
reset(f);
read(f,n);
for i:=1 to n do
read(f,a[i],nr[i]);
read(f,p);
close(f);
end;

procedure back(k:integer);
var i,j:integer;
begin
st[k]:=-1;
for i:=0 to nr[k] do
begin
inc(st[k]);
if i<>0 then s:=s+a[k];
if s<=p then
begin
if k=n then
begin
if s=p then
begin
inc(l);
writeln('Solution ',l);
for j:=1 to n do
if st[j]<>0 then writeln(st[j],' coins of type ',j);
writeln;
end;
end
else back(k+1);
end;
if (i=nr[k]) or (s>p) then begin s:=s-st[k]*a[k]; i:=nr[k]; end;
end;
end;

begin
readdata;
l:=0;
s:=0;
back(1);
end.

 

C++ program:

Iterative version:

#include<iostream.h>
#include<fstream.h>
void main()
{
int a[100],st[100],nr[100],s,max,i,j,k,l,m,n,p,cond;
fstream f("in.txt", ios::in);
f>>n;
max=0;
for (i=1;i<=n;i++)
{
f>>a[i]>>nr[i];
if (max<nr[i]) {max=nr[i];}
}
f>>p;
k=1; //we start from the first type of coin
st[k]=-1; //we initialize the number of coins of that type with -1,
//so that by incrementing we can have from 0 to the maximum possible number of coins
s=0; // the sum of the value of the coins
l=0; //the number of solutions found so far
do
{
while (st[k]<max)
{
st[k]+=1;
cond=1;
if (st[k]>nr[k]){cond=0;} // if the number of coins taken is bigger than the number of coins given
if (st[k]!=0) {s+=a[k];}
if (s>p) {cond=0;}
if (cond==1)
{
if (k==n)
{
if (s==p)
{
l+=1;
cout<<"Solution "<<l<<endl;
for (i=1;i<=n;i++)
if (st[i]!=0) {cout<<st[i]<<" coins of type "<<i<<endl;}
cout<<endl;
}
}
else
{
k+=1; // moving to the next type of coins
st[k]=-1;
}
}
}
s-=st[k]*a[k];
k-=1;
}
while (k!=0); //going down to the previous type of coins to try another number
}

Recursive version:

#include<iostream.h>
#include<fstream.h>
int a[100],nr[100],st[100],i,j,k,l,m,n,p,s;
fstream f("in.txt", ios::in);

void readdata()
{
f>>n;
for (i=1;i<=n;i++)
f>>a[i]>>nr[i];
f>>p;
f.close();
}

void back(int k)
{
int i,j;
st[k]=-1;
for(i=0;i<=nr[k];i++)
{
st[k]+=1;
if (i!=0) {s+=a[k];}
if (s<=p)
{
if (k==n)
{
if (s==p)
{
l+=1;
cout<<"Solution "<<l<<endl;
for (j=1;j<=n;j++)
if (st[j]!=0) {cout<<st[j]<<" coins of type "<<j<<endl;}
}
}
else {back(k+1);}
}
if ((i==nr[k])||(s>p)) {s-=st[k]*a[k]; i=nr[k];}
}
}

void main()
{
readdata();
l=0;
s=0;
back(1);
}