Sum of 5 numbers = 100

Question

So, you are given 10 numbers and your are supposed to choose 5 numbers out of those so that the sum is 100.

Now, I obviously tried to solve it using a program and got the obvious solution with five loops. But I just wanted to know is there any efficient way to do this?

Here is Mr. Obvious :

        static void Main(string[] args)
        {
            int[] a = { 2, 6, 10, 14, 18, 22, 26, 30, 34, 38 };
            for (int f = 0; f < a.Length - 4; f++)
            {
                for (int s = f+1; s < a.Length - 3; s++)
                {
                    for (int t = s+1; t < a.Length - 2; t++)
                    {
                        for (int fr = t + 1; fr < a.Length - 1; fr++)
                        {
                            for (int ft = fr + 1; ft < a.Length; ft++)
                            {
                                int sum = a[f] + a[s] + a[t] + a[fr] + a[ft];
                                Console.WriteLine(sum);
                                if (sum == 100)
                                {
                                    Console.WriteLine("---------------------------------------");
                                    Console.WriteLine(a[f]);
                                    Console.WriteLine(a[s]);
                                    Console.WriteLine(a[t]);
                                    Console.WriteLine(a[fr]);
                                    Console.WriteLine(a[ft]);
                                    Console.WriteLine("---------------------------------------");
                                }
                            }

                        }
                    }
                }
            }
            Console.ReadLine();
        }

Why have you put several different languages as tags? What do you want the answer in? — Arran, Mar 14 '13 at 13:26
Seems like a job for dynamic programming. Maybe a variation of the Knapsack problem? — Óscar López, Mar 14 '13 at 13:26
@Arran it doesn't matter which language the answer is in as this is just out of curiosity.. and I understant those 4 languages is all... — Aditi, Mar 14 '13 at 13:27
Possible dup? http://stackoverflow.com/questions/4632322/finding-all-possible-combinations-of-numbers-to-reach-a-given-sum and they cover almost all the languages in this one, although I did not see C++ — Shafik Yaghmour, Mar 14 '13 at 13:27
You can see a solution to a similar 4-Sum problem from this thread: http://stackoverflow.com/questions/11216582/4sum-implementation-in-java-from-leetcode. Your question is then 5-sum. — taocp, Mar 14 '13 at 13:27
@Aditi, that's fine, but make that a bit clearer in your question. From a distance, without reading your comment there, it literally looks like you couldn't make up your mind what language to do this in or you have no idea how to use tags. — Arran, Mar 14 '13 at 13:28
Its a subset sum problem. Solved using dynamic programming. [SO link](http://stackoverflow.com/questions/4355955/subset-sum-algorithm) — Bhaskar, Mar 14 '13 at 13:28
@Belogix No it's ot homework... if it was, I already have my answer. It just so happens that I got this puzzle somewhere and thought "i wud rather write a program than do all those calculations!" :P — Aditi, Mar 14 '13 at 13:28
If you tag every language, you probably meant to just tag it with algorithm and make it language agnostic. — Mike, Mar 14 '13 at 13:29
I don't see a reason for those snobbish comments, this is a generic CS problem, language agnostic. To OP: This is an NP-Complete problem and whatever way you solve it, you'll get exponential complexity. Unless you use some sort of approximation algorithm of course. — , Mar 14 '13 at 13:29
This is quite different from the standard subset sum problem. In this case you know the answer requires 5 numbers. Using this fact more efficient solutions are possible. — Erik, Mar 14 '13 at 13:30
@HovercraftFullOfEels :) I can't imagine what if SO allows like 10-15 tags for each question.. — Soner Gönül, Mar 14 '13 at 13:30
Do you want to find just a single solution or do you want to find all possible solutions? — Erik, Mar 14 '13 at 13:33
@Erik I just want to find the most efficient solution... because using all these loops seems just stupid. :P — Aditi, Mar 14 '13 at 13:34

MrSmith42 · Answer 1 · 2013-03-17T14:14:16.003

Here some optimization-ideas:

If all numbers are positive, you can skip inner loops, of the sum is already >= 100
you can reduce the calculations by calculating partial sums in each loop (values of outer loops do not change while running the inner loops).

calculate a.Length only once and store it because this value never changes

static void Main(string[] args)
{
    int[] a = { 2, 6, 10, 14, 18, 22, 26, 30, 34, 38 };
    int lenA=a.Length;
    int alenMinus4=lenA-4,
    int alenMinus3=lenA-3,
    int alenMinus2=lenA-2,
    int alenMinus1=lenA-1,

    for (int f = 0; f < alenMinus4; f++)
    {   int sum1=a[f];
        if(sum1>100)
        { f=alenMinus4;
        }
        else
        {   for (int s = f+1; s < alenMinus3; s++)
            {   int sum2=sum1+ a[s];
                if(sum2>100)
                { s=alenMinus3;
                }
                else
                {   for (int t = s+1; t < alenMinus2; t++)
                    {   int sum3=sum2+ a[t];
                        if(sum3>100)
                        { t=alenMinus2;
                        }
                        else
                        {   for (int fr = t + 1; fr < alenMinus1; fr++)
                            {   int sum4=sum3+ a[fr];
                                if(sum4>100)
                                { fr=alenMinus1;
                                }
                                else
                                {  for (int ft = fr + 1; ft < lenA; ft++)
                                    {   int sum = sum4 + a[ft];
                                        Console.WriteLine(sum);
                                        if (sum == 100)
                                        {   Console.WriteLine("---------------------------------------");       
                                            Console.WriteLine(a[f]);
                                            Console.WriteLine(a[s]);
                                            Console.WriteLine(a[t]);
                                            Console.WriteLine(a[fr]);
                                            Console.WriteLine(a[ft]);
                                            Console.WriteLine("---------------------------------------");
    }   }   }   }   }   }   }   }   }   }
    Console.ReadLine();
}

Hopefully the compiler can do your optimizations 2) and 3), and only 1) requires any new code. — Marc Glisse, Mar 14 '13 at 13:35
@Marc Glisse: The compilor might [I would not count on it] make the optimization 3) [If it is smart enough to detect that this never changes]. I bet the compilor will not detect that parts of the sum `a[f] + a[s] + a[t] + a[fr] + a[ft]` can be moved to the outer loops. And as you agreed on, the 1) optimization, which will increase the speed the most, will need human change of code. — MrSmith42, Mar 14 '13 at 13:46

score 0 · Answer 2 · edited May 23 '17 at 10:25

0

You can use combinations. Check out this question: creating all possible k combinations of n items in C++

In this case you have n numbers, and k indices of numbers to choose from.

This should cut the number of iterations down.

edited May 23 '17 at 10:25

Community

1
1

answered Mar 14 '13 at 13:31

Boyko Perfanov

3,007
18
34

Sum of 5 numbers = 100

2 Answers2