Algorithm for finding a group of numbers in a list that equal a target

Question

So here is what I'm trying to do. I have a list of integers:

List<int> myList = new List<int>() {5,7,12,8,7};

And I also got a target:

int target = 20;

What I'm trying to do is find a way to create a new list of integer that when added together equal my target. So if my target is 20, I need a list like this:

{ 12, 8 }

If my target is 26, then I'll have this:

{ 7, 12, 7 }

Each number can only be used one time (7 is used twice because its in the list twice). If there is no solution, it should return an empty list. Anyone have any idea how I can do something like this?

Answer 1

That's a statistical problem. You want to find all possible combinations with a matching sum. I can recommend this project which is also worth reading:

http://www.codeproject.com/Articles/26050/Permutations-Combinations-and-Variations-using-C-G

Then it's easy and efficient:

List<int> myList = new List<int>() { 5, 7, 12, 8, 7 };
var allMatchingCombos = new List<IList<int>>();
for (int lowerIndex = 1; lowerIndex < myList.Count; lowerIndex++)
{
    IEnumerable<IList<int>> matchingCombos = new Combinations<int>(myList, lowerIndex, GenerateOption.WithoutRepetition)
        .Where(c => c.Sum() == 20);
    allMatchingCombos.AddRange(matchingCombos);
}

foreach(var matchingCombo in allMatchingCombos)
    Console.WriteLine(string.Join(",", matchingCombo));

Output:

12,8
5,7,8
5,8,7

Answer 2

You can find all the solutions given below here: https://github.com/Mr-Zoidberg/Find-Possible-Combinations

1. Using recursion

static void Main(string[] args)
    {
        const int target = 20;
        var numbers = new List<int> { 1, 2, 5, 8, 12, 14, 9 };

        Console.WriteLine($"Number of Combinations: {SumCounter(numbers, target)}");
        Console.ReadKey();
    }


    private static int SumCounter(IReadOnlyList<int> numbers, int target)
    {
        var result = 0;
        RecursiveCounter(numbers, target, new List<int>(), ref result);
        return result;
    }

    private static void RecursiveCounter(IReadOnlyList<int> numbers, int target, List<int> partial, ref int result)
    {
        var sum = partial.Sum();
        if (sum == target)
        {
            result++;
            Console.WriteLine(string.Join(" + ", partial.ToArray()) + " = " + target);
        }

        if (sum >= target) return;

        for (var i = 0; i < numbers.Count; i++)
        {
            var remaining = new List<int>();
            for (var j = i + 1; j < numbers.Count; j++) remaining.Add(numbers[j]);
            var partRec = new List<int>(partial) { numbers[i] };
            RecursiveCounter(remaining, target, partRec, ref result);
        }
    }

2. Get subsets using Linq

static void Main(string[] args)
    {
        const int target = 20;
        var numbers = new int[] { 1, 2, 5, 8, 12, 14, 9 };

        var matches = numbers.GetSubsets().Where(s => s.Sum() == target).ToArray();

        foreach (var match in matches) Console.WriteLine(match.Select(m => m.ToString()).Aggregate((a, n) => $"{a} + {n}") + $" = {target}");

        Console.WriteLine($"Number of Combinations: {matches.Length}");
        Console.ReadKey();
    }
}

public static class Extension
{
    public static IEnumerable<IEnumerable<T>> GetSubsets<T>(this IEnumerable<T> collection)
    {
        if (!collection.Any()) return Enumerable.Repeat(Enumerable.Empty<T>(), 1);
        var element = collection.Take(1);
        var ignoreFirstSubsets = GetSubsets(collection.Skip(1));
        var subsets = ignoreFirstSubsets.Select(set => element.Concat(set));
        return subsets.Concat(ignoreFirstSubsets);
    }

3. Another recursive method...

static void Main(string[] args)
    {
        const int target = 20;
        var numbers = new [] { 1, 2, 5, 8, 12, 14, 9 };
        var result = GetSubsets(numbers, target, "");

        foreach (var subset in result) Console.WriteLine($"{subset} = {target}");
        Console.WriteLine($"Number of Combinations: {result.Count()}");
        Console.ReadLine();
    }

    public static IEnumerable<string> GetSubsets(int[] set, int sum, string values)
    {
        for (var i = 0; i < set.Length; i++)
        {
            var left = sum - set[i];
            var vals = values != "" ? $"{set[i]} + {values}" : $"{set[i]}";
            if (left == 0) yield return vals;
            else
            {
                int[] possible = set.Take(i).Where(n => n <= sum).ToArray();
                if (possible.Length <= 0) continue;
                foreach (string s in GetSubsets(possible, left, vals)) yield return s;
            }
        }
    }

4. Using binary search. Linear time.

static void Main(string[] args)
    {
        const int target = 20;
        var numbers = new [] { 1, 2, 5, 8, 12, 14, 9 };

        var subsets = GetSubsets(numbers, target);

        foreach (var s in subsets) Console.WriteLine($"{s} = {target}");
        Console.WriteLine($"Number of Combinations: {subsets.Count()}");
        Console.ReadKey();
    }


    private static IEnumerable<string> GetSubsets(int[] array, int target)
    {      
        Array.Sort((Array)array);
        List<string> result = new List<string>();

        for (int i = array.Length-1; i >= 0; i--)
        {
            var eq = $"{array[i]}";
            var sum = array[i];
            var toAdd = 0;

            while (sum != target)
            {
                var mid = Array.BinarySearch(array, 0, sum <= target / 2 && sum != array[i] ? array.Length - 1 : i, target - sum);
                mid = mid < 0 ? ~mid - 1 : mid;
                if (mid == i  || mid < 0 || toAdd == array[mid] ) break;

                toAdd = array[mid];
                sum += array[mid];
                eq += $" + {array[mid]}";
                if (sum == target) result.Add(eq);
            }
        }
        return result;
    }

Answer 3

Using recursion. Note that this solution will favor solutions that can be acquired by using the first items from the list. So for a target of 20, you won’t get 12+8 as the solution but 5+7+8.

List<int> findSum(List<int> numbers, int target, int index = 0)
{
    // loop through all numbers starting from the index
    for (var i = index; i < numbers.Count; i++)
    {
        int remainder = target - numbers[i];
        // if the current number is too big for the target, skip
        if (remainder < 0)
            continue;
        // if the current number is a solution, return a list with it
        else if (remainder == 0)
            return new List<int>() { numbers[i] };
        else
        {
            // otherwise try to find a sum for the remainder later in the list
            var s = findSum(numbers, remainder, i + 1);

            // if no number was returned, we could’t find a solution, so skip
            if (s.Count == 0)
                continue;

            // otherwise we found a solution, so add our current number to it
            // and return the result
            s.Insert(0, numbers[i]);
            return s;
        }
    }

    // if we end up here, we checked all the numbers in the list and
    // found no solution
    return new List<int>();
}

void Main()
{
    List<int> myList = new List<int>() { 5, 7, 12, 8, 7 };

    Console.WriteLine(findSum(myList, 12)); // 5, 7
    Console.WriteLine(findSum(myList, 20)); // 5, 7, 8
    Console.WriteLine(findSum(myList, 31)); // 5, 7, 12, 7
}

Answer 4

This implementation of mine in C# will return all combinations(including repetitive use of same number) that equals a given number.

string r;
List<int> l = new List<int>();
void u(int w, int s, int K, int[] A) { 
    // If a unique combination is found 
    if (s == K) { 
        r += "(" + String.Join(" ", l) + ")";
        return; 
    } 
    // For all other combinations
    for (int i=w; i<A.Length; i++){
        // Check if the sum exceeds K 
        int x = A[i];
        if (s + x <= K){
            l.Add(x);
            u(i, s + x, K,A);
            l.Remove(x);
        }
    }
} 
string combinationSum(int[] a, int s) {
    r = "";
    u(0, 0, s, a.Distinct().OrderBy(x=>x).ToArray());
    return r.Any() ? r : "Empty";
}

for a: [2, 3, 5, 9] and s = 9

the result will be : "(2 2 2 3)(2 2 5)(3 3 3)(9)"