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

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 2

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