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;
using System.Threading;

/// <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;
    static readonly Func<ConsoleKeyInfo> ReadKey = Console.ReadKey;

    // Composition root
    static void Main(string[] args)
    {
        Thread.CurrentThread.CurrentCulture = CultureInfo.GetCultureInfo("en-US");

        // 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));

        ReadKey();
    }
}

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
{
    readonly Action<object> _write;
    private readonly Data _p;
    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)
    {
        P.Add(c);
        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 + ", "));
            P.SolutionsList.Add(string.Format("Numbers: {0}\nIndexes: {1}\n\n", numbers, indexes));
        }


        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)
    public void Add(Candidate c)
    {
        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));
            }
            SetPathsTried.Add(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

Advertisements