Sum array values with sum equals X.

Question

I have an integer collection. I need to get all possibilites that sum of values are equal to X.

I need something like this.

It can be written in: delphi, c#, php, RoR, python, cobol, vb, vb.net

Answer 1

That's a subset sum problem. And it is NP-Complete.

The only way to implement this would be generate all possible combinations and compare the sum values. Optimization techniques exists though.

Here's one in C#:

static class Program
{
    static int TargetSum = 10;
    static int[] InputData = new[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };

    static void Main()
    {
        // find all permutations
        var permutations = Permute(InputData);

        // check each permutation for the sum
        foreach (var item in permutations) {

            if (item.Sum() == TargetSum) {

                Console.Write(string.Join(" + ", item.Select(n => n.ToString()).ToArray()));
                Console.Write(" = " + TargetSum.ToString());
                Console.WriteLine();

            }
        }

        Console.ReadKey();
    }

    static IEnumerable<int[]> Permute(int[] data) { return Permute(data, 0); }

    static IEnumerable<int[]> Permute(int[] data, int level)
    {
        // reached the edge yet? backtrack one step if so.
        if (level >= data.Length) yield break;

        // yield the first #level elements
        yield return data.Take(level + 1).ToArray();

        // permute the remaining elements
        for (int i = level + 1; i < data.Length; i++) {
            var temp = data[level];
            data[level] = data[i];
            data[i] = temp;

            foreach (var item in Permute(data, level + 1))
                yield return item;

            temp = data[i];
            data[i] = data[level];
            data[level] = temp;
        }

    }
}

Answer 2

Dynamic Programming would yield the best runtime for an exact solution. The Subset Sum Problem page on Wikipedia has some pseudo-code for the algorithm. Essentially you order all the numbers and add up all the possible sequences in order such that you minimize the number of additions. The runtime is pseudo-polynomial.

For a polynomial algorithm you could use an Approximation Algorithm. Pseudo-code is also available at the Subset Sum Problem page.

Of the two algorithms I would choose the dynamic programming one since it is straight-forward and has a good runtime with most data sets.

However if the integers are all non-negative and fit with the description on the Wikipedia page then you could actually do this in polynomial time with the approximation algorithm.