# Software Programming

Kunuk Nykjaer

## Backtracking – Subset sum with C#

Here’s an example of backtracking algorithm implemented in C#.
This solves the Subset sum

Subset sum problem is NP-complete and depending on your data set the running time can be very slow.

program.cs

```using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Globalization;
using System.Linq;

/// <summary>
/// Author: Kunuk Nykjaer
/// Backtracking Algorithm in C#
/// Subset sum
///
/// With list numbers and a given sum value
/// Find subset of list which adds up to the given sum value.
/// </summary>
public class Program
{
static readonly Action<object> Write = Console.Write;

// Composition root
static void Main(string[] args)
{

// Use timer for checking algo time
var sw = new Stopwatch();
sw.Start();

// -----------------------------------------
// ** INSERT YOUR DATA HERE **
// Init config,
var config = new Config
{
MaxSolutions = 1,          // restrict result count
ShowProgress = true,       // show backtrack progress
ShowStatus = true,         // show iteration progress
DisplaySolutions = true,   // Show solution list
DetectCodeError = false,   // slower running time if true
};

// set
var set = new List<float> { -7, -3, -2, 5, 8 };

// subset sum
var sum = 0;

// ** END INSERT DATA **
// -----------------------------------------

// Init data
var P = new Data(set, sum, config);

// Init backtrack algo
var bt = new Backtrack(Write, P);

// Find solutions
bt.Run();

// Algo done, stop time
sw.Stop();

// Show results
bt.Show();

Write(string.Format("\nSec: {0}\nPress a key to exit\n",
sw.ElapsedMilliseconds / 1000d));

}
}

class Config
{
public int MaxSolutions { get; set; }
public bool ShowProgress { get; set; }
public bool ShowStatus { get; set; }
public bool DisplaySolutions { get; set; }
public bool DetectCodeError { get; set; }
public Config() { MaxSolutions = 1; }
}

class Backtrack
{
private bool _maxSolutionsReachedExitBt;

public Backtrack(Action<object> write, Data P)
{
_write = write;
_p = P;
}

void UndoUpdate(Data P, Candidate c, int depth)
{
P.Remove(c);
if (P.Config.ShowProgress) { Print(P, c, depth); }
}

void Update(Data P, Candidate c, int depth)
{
if (P.Config.ShowProgress) { Print(P, c, depth); }
}

/*
wikipedia:
http://en.wikipedia.org/wiki/Backtracking

procedure bt(P,c)
if reject(P,c) then return
update(P,c) // update data
if accept(P,c) then output(P,c)
s ← first(P,c)
while s ≠ Λ do
bt(P,s)
s ← next(P,s)
end while
undoUpdate(P,c) // backtracking starts here
end procedure
*/

// O(?)
void Bt(Data P, Candidate c, int depth)
{
if (Reject(P, c)) { return; }

// Update data
Update(P, c, depth);

if (P.Config.ShowStatus) { ShowStatus(P, c); } // print status

if (Accept(P, c)) { SaveResult(P, c); }

if (_maxSolutionsReachedExitBt) { return; } // custom exit

var s = First(P, c);

while (s != null)
{
Bt(P, s, depth + 1);
s = Next(P, s);
}

if (_maxSolutionsReachedExitBt) { return; } // custom exit

// Leaf, dead end, backtrack, roll back data
UndoUpdate(P, c, depth);
}

// O(1)
bool Accept(Data P, Candidate c)
{
const float epsilon = 0.000001f;
if (Math.Abs(P.Sum - P.WorkingSum) < epsilon) { return true; }

return false;
}

// O(1)
bool Reject(Data P, Candidate c)
{
if (_maxSolutionsReachedExitBt) { return true; }

if (c == null) { throw new ArgumentNullException("c"); }

var i = P.Numbers[c.Index];

// Optimization vs. iterate all combinations
// Reject if rest of sorted list contains positive numbers
if (i >= 0 && i + P.WorkingSum > P.Sum){ return true; }

return false;
}

public void Run()
{
var setsum = _p.Numbers.Sum();
if (_p.Sum > setsum)
{
_write(string.Format("Sum: {0} is bigger than set sum {1}, no solutions exists\n",
_p.Sum, setsum));
return;
}

for (int i = 0; i < _p.Numbers.Length; i++)
{
Bt(_p, new Candidate { Index = i }, 1);
}
}

public void Show()
{
_write(string.Format("Max solutions: {0}\n", _p.Config.MaxSolutions));
_write(string.Format("Sum: {0}\n", _p.Sum));
_write(string.Format("Set:\n"));
_p.Numbers.ToList().ForEach(a => _write(a + ", "));

if (_p.Config.DisplaySolutions)
{
_write(string.Format("\n\n*** Solutions:\n\n"));
_p.SolutionsList.ForEach(_write);
}

_write(string.Format("\nUnique Paths Tried: {0}\n", _p.PathsTried));
_write(string.Format("Solutions count: {0}\n", _p.Solutions));
}

// O(n) where n is path length
void SaveResult(Data P, Candidate c)
{
P.Solutions++;

if (P.Config.DisplaySolutions)
{
// Only save result data if to be displayed
var list = P.Stack.ToList();
list.Reverse();

string numbers = list.Aggregate("", (a, b) => a + (P.Numbers[b] + ", "));
string indexes = list.Aggregate("", (a, b) => a + (b + ", "));
}

if (P.Solutions >= P.Config.MaxSolutions) { _maxSolutionsReachedExitBt = true; }
}

// First valid child from path
// O(1)
Candidate First(Data P, Candidate c)
{
int j = c.Index + 1;
if (j >= P.Numbers.Length) { return null; }

return new Candidate { Index = j };
}

// Next sibling from current leaf
// O(1)
Candidate Next(Data P, Candidate c)
{
int j = c.Index + 1;
if (j >= P.Numbers.Length) { return null; }

return new Candidate { Index = j };
}

void Print(Data P, Candidate c, int depth)
{
_write(string.Format("path: {0}  \tsum: {1}  \tdepth: {2}\n",
P.Path.Get(), P.WorkingSum, depth));
}

void ShowStatus(Data P, Candidate c)
{
// Debug
if (P.PathsTried % 500000 == 0)
{
_write(string.Format("Paths tried: {0:n0}  \tSolutions: {1}  \tPath: {2}\n",
P.PathsTried, P.Solutions, P.Path.Get()));
}
}
}

class Candidate
{
public int Index { get; set; }
public override string ToString()
{
return string.Format("{0}", Index);
}
}

class Data
{
// Init data
public Config Config;
public float Sum { get; private set; }
public float[] Numbers { get; private set; }

// Backtracking data
public bool[] Path { get; private set; }
public float WorkingSum { get; private set; }
public Stack<int> Stack = new Stack<int>();

// Result data
public int PathsTried;
public List<string> SolutionsList = new List<string>();
public int Solutions { get; set; }

// Only used for Detect code error
public HashSet<string> SetPathsTried = new HashSet<string>();

public Data(List<float> numbers, float sum, Config config)
{
numbers.Sort(); // sort is used for reject condition in bt algo
Numbers = numbers.ToArray();
Path = new bool[Numbers.Length];
Sum = sum;
Config = config;
}

// O(1)
public void Remove(Candidate c)
{
if (c == null) { throw new ArgumentNullException("c"); }

var i = Stack.Pop();
UpdatePath(false, i);
WorkingSum -= Numbers[i];
}

// O(1) (or O(n) if detectCodeError)
{
if (c == null) { throw new ArgumentNullException("c"); }

UpdatePath(true, c.Index);
WorkingSum += Numbers[c.Index];
Stack.Push(c.Index);
PathsTried++;

if (Config.DetectCodeError)
{
var path = Stack.GetString(); // O(n) where n is stack count
if (SetPathsTried.Contains(path)) // O(1)
{
throw new ApplicationException(string.Format("Path already visited: {0}", path));
}
}
}

// O(1)
void UpdatePath(bool value, int index)
{
if (Path[index] == value)
{
throw new ApplicationException(string.Format("Path already set for index: {0}, value: {1}",
index, Numbers[index]));
}
Path[index] = value;
}
}

static class Extensions
{
public static string GetString<T>(this IEnumerable<T> arr)
{
return arr.Aggregate("", (a, b) => a + string.Format("{0}->", b));
}
public static string Get(this IEnumerable<bool> arr)
{
return arr.Aggregate("", (a, b) => a + (b ? "1" : "0"));
}
}
```

## Examples of usage and results

### Set including negative numbers

Find subset sum from set with negative and positive numbers.

Configuration is set as:
– MaxSolutions = 3,
– ShowProgress = false,
– ShowStatus = true,
– DisplaySolutions = true

```Max solutions: 3
Sum: 100
Set:
-10, -1, 1, 2, 5, 10, 20, 20, 30, 40, 50,

*** Solutions:

Numbers: -10, -1, 1, 10, 20, 30, 50,
Indexes: 0, 1, 2, 5, 6, 8, 10,

Numbers: -10, -1, 1, 10, 20, 30, 50,
Indexes: 0, 1, 2, 5, 7, 8, 10,

Numbers: -10, -1, 1, 20, 20, 30, 40,
Indexes: 0, 1, 2, 6, 7, 8, 9,

Unique Paths Tried: 162
Solutions count: 3

Sec: 0.007
```

### Solutions count only

Here we are interested of numbers of subset sum matching the sum value.

Configuration is set as:
– MaxSolutions = int.MaxValue,
– ShowProgress = false,
– ShowStatus = true,
– DisplaySolutions = false

```Paths tried: 500.000    Solutions: 14810   Path: 110111010011000000110000000
Paths tried: 1.000.000  Solutions: 28743   Path: 101111011001111010011000000
Paths tried: 1.500.000  Solutions: 42862   Path: 100111010101001000001000000
Paths tried: 2.000.000  Solutions: 56129   Path: 100000000000000101110100000
Paths tried: 2.500.000  Solutions: 70302   Path: 010111110101101001100000000
Paths tried: 3.000.000  Solutions: 83851   Path: 010000010100111010010010000
Paths tried: 3.500.000  Solutions: 97535   Path: 001000100111100010000000000
Paths tried: 4.000.000  Solutions: 110731  Path: 000001011010011000111000000
Max solutions: 2147483647
Sum: 500
Set:
10, 10, 15, 15, 20, 20, 25, 25, 30, 30, 35, 35, 40, 40, 45, 45, 50,
50, 55, 60, 65, 100, 200, 300, 400, 500, 600,

Unique Paths Tried: 4114568
Solutions count: 113508

Sec: 3.639
```

### Floating numbers

```Max solutions: 5
Sum: 3
Set:
-1, 0.1, 0.2, 0.5, 1, 1.5, 2, 2.5, 2.9,

*** Solutions:

Numbers: -1, 0.1, 1, 2.9,
Indexes: 0, 1, 4, 8,

Numbers: -1, 0.5, 1, 2.5,
Indexes: 0, 3, 4, 7,

Numbers: -1, 0.5, 1.5, 2,
Indexes: 0, 3, 5, 6,

Numbers: -1, 1.5, 2.5,
Indexes: 0, 5, 7,

Numbers: 0.1, 2.9,
Indexes: 1, 8,

Unique Paths Tried: 98
Solutions count: 5
```

Written by kunuk Nykjaer

December 25, 2012 at 2:22 pm

Posted in Algorithm, Csharp

Tagged with , ,