Algorithm to find which numbers from a list of size n sum to another number

Question

I have a decimal number (let's call it goal) and an array of other decimal numbers (let's call the array elements) and I need to find all the combinations of numbers from elements which sum to goal.

I have a preference for a solution in C# (.Net 2.0) but may the best algorithm win irrespective.

Your method signature might look something like:

public decimal[][] Solve(decimal goal, decimal[] elements)

Answer 1

Interesting answers. Thank you for the pointers to Wikipedia - whilst interesting - they don't actually solve the problem as stated as I was looking for exact matches - more of an accounting/book balancing problem than a traditional bin-packing / knapsack problem.

I have been following the development of stack overflow with interest and wondered how useful it would be. This problem came up at work and I wondered whether stack overflow could provide a ready-made answer (or a better answer) quicker than I could write it myself. Thanks also for the comments suggesting this be tagged homework - I guess that is reasonably accurate in light of the above.

For those who are interested, here is my solution which uses recursion (naturally) I also changed my mind about the method signature and went for List> rather than decimal[][] as the return type:

public class Solver {

    private List<List<decimal>> mResults;

    public List<List<decimal>> Solve(decimal goal, decimal[] elements) {

        mResults = new List<List<decimal>>();
        RecursiveSolve(goal, 0.0m, 
            new List<decimal>(), new List<decimal>(elements), 0);
        return mResults; 
    }

    private void RecursiveSolve(decimal goal, decimal currentSum, 
        List<decimal> included, List<decimal> notIncluded, int startIndex) {

        for (int index = startIndex; index < notIncluded.Count; index++) {

            decimal nextValue = notIncluded[index];
            if (currentSum + nextValue == goal) {
                List<decimal> newResult = new List<decimal>(included);
                newResult.Add(nextValue);
                mResults.Add(newResult);
            }
            else if (currentSum + nextValue < goal) {
                List<decimal> nextIncluded = new List<decimal>(included);
                nextIncluded.Add(nextValue);
                List<decimal> nextNotIncluded = new List<decimal>(notIncluded);
                nextNotIncluded.Remove(nextValue);
                RecursiveSolve(goal, currentSum + nextValue,
                    nextIncluded, nextNotIncluded, startIndex++);
            }
        }
    }
}

If you want an app to test this works, try this console app code:

class Program {
    static void Main(string[] args) {

        string input;
        decimal goal;
        decimal element;

        do {
            Console.WriteLine("Please enter the goal:");
            input = Console.ReadLine();
        }
        while (!decimal.TryParse(input, out goal));

        Console.WriteLine("Please enter the elements (separated by spaces)");
        input = Console.ReadLine();
        string[] elementsText = input.Split(' ');
        List<decimal> elementsList = new List<decimal>();
        foreach (string elementText in elementsText) {
            if (decimal.TryParse(elementText, out element)) {
                elementsList.Add(element);
            }
        }

        Solver solver = new Solver();
        List<List<decimal>> results = solver.Solve(goal, elementsList.ToArray());
        foreach(List<decimal> result in results) {
            foreach (decimal value in result) {
                Console.Write("{0}\t", value);
            }
            Console.WriteLine();
        }


        Console.ReadLine();
    }
}

I hope this helps someone else get their answer more quickly (whether for homework or otherwise).

Cheers...

Answer 2

The subset-sum problem, and the slightly more general knapsack problem, are solved with dynamic programming: brute-force enumeration of all combinations is not required. Consult Wikipedia or your favourite algorithms reference.

Although the problems are NP-complete, they are very "easy" NP-complete. The algorithmic complexity in the number of elements is low.

Answer 3

I think you've got a bin packing problem on your hands (which is NP-hard), so I think the only solution is going to be to try every possible combination until you find one that works.

Edit: As pointed out in a comment, you won't always have to try every combination for every set of numbers you come across. However, any method you come up with has worst-case-scenario sets of numbers where you will have to try every combination -- or at least a subset of combinations that grows exponentially with the size of the set.

Otherwise, it wouldn't be NP-hard.

Answer 4

You have described a knapsack problem, the only true solution is brute force. There are some approximation solutions which are faster, but they might not fit your needs.

Answer 5

While not solving the problem of brute force (as others already mentioned) you might want to sort your numbers first, and then go over the possible ones left (since once you passed Sum value, you can't add any number larger than Goal - Sum).

This will change the way you implement your algorithm (in order to sort only once and then skip marked elements), but on the average would improve performance.

Answer 6

public class Logic1 {
    static int val = 121;
    public static void main(String[] args)
    {
        f(new int[] {1,4,5,17,16,100,100}, 0, 0, "{");
    }

    static void f(int[] numbers, int index, int sum, String output)
    {
        System.out.println(output + " } = " + sum);
        //System.out.println("Index value1 is "+index);
        check (sum);
        if (index == numbers.length)
        {
            System.out.println(output + " } = " + sum);
            return;
        }

        // include numbers[index]
        f(numbers, index + 1, sum + numbers[index], output + " " + numbers[index]);
        check (sum);
        //System.out.println("Index value2 is "+index);
        // exclude numbers[index]
        f(numbers, index + 1, sum, output);
        check (sum);
    }

    static void check (int sum1)
    {
        if (sum1 == val)
            System.exit(0);
    }
}