1

Given the number 15 and the array [1, 2, 3, 4, 5, 6]

Possible combinations (sum=15) would be:
[1, 2, 3, 4, 5]
[2, 3, 4, 6]
[1, 3, 5, 6]
[4, 5, 6]

Their respective sum of squares would be:
55, 65, 71 and 77

Any number in the array can only be used once in any of the number combinations (no repeating numbers). The solution would be the number combination with the smallest sum of squares (i.e. 55)

What could be an efficient logic to solve this problem?

So far, I've tried this:

Nested for loops:

for (j=0; j<arrLength; j++){
    sum = 0;
    for (i=j; i<arrLength; i++){
        sum+=arrNumbers[i];
        if (sum >= 15) {break;}
    }
}
if (sum == 15) {
    for(j=j; j<=i; j++){
    printf("%d ", arrNumbers[j]);
}

However, that doesn't always give the correct results because it only checks number combinations in succession (e.g. [1, 2, 3], [2, 3, 4], [3, 4, 5])

After that, I tried this:

for (j=0; j<arrLength; j++){
    sum = 0;
    for (k=j; k<arrLength; k++){
        if (sum == 15) {break;}
        sum=arrNumbers[j];
        for (i=k+1; i<arrLength; i++){
            sum+=arrNumbers[i];
            if (sum >= 15) {break;}
        }
    }
    if (sum >= 15) {break;}
}
if(sum==15){
    //print number combinations here
}

That didn't work either as I learnt later that it isn't quite different from the first solution and my logic is flawed.

What I'm having trouble with is trying to think of a logic that iterates through all the numbers in the array (regardless of order) to find combinations that add up to the number 15.

For instance, my code can find these combinations if they are in sequential order [1, 2, 3, 4, 5] or [4, 5, 6] but it can't find something like [1, 3, 5, 6].

  • 1
    What have you tried thus far? Also, please read this – World Engineer Sep 18 '14 at 3:52
  • @WorldEngineer Thanks for the link! This was indeed a homework question (that someone asked me to solve). However, the due date has passed and I'm not really interested in the urgency of the solution nor am I interested in getting a complete solution. I'd just like to understand how to go about solving this. I've updated the question with the stuff I've tried. – Vinayak Sep 18 '14 at 4:57
  • 2
    Essentially, you want to iterate over all subsets of a set. The top answer here explains who to do so with a bitmask: stackoverflow.com/questions/22280078/… – Chris Pitman Sep 18 '14 at 5:12
  • How about just picking numbers 1, 2, 3, ... until the sum exceeds the given number n. Then drop the largest number and choose the second largest number so that the sum equals n. Isn't this sufficient since since the finest "partitioning" produces always the lowest sum of squares? (a + b = c --> a^2 + b^2 <= c^2) – COME FROM Sep 18 '14 at 12:48
2

One possible approach is to generate all combinations (or subsets) of the array (google for "generate combinations c" or "generate subsets c" and you will find plenty of examples).

Then you add up the elements of each combination, check if the sum is equal to 15, and if that's true, keep the combination for the "lowest sum of squares" test.

The drawback of this approach is that if you try to process bigger arrays, it becomes very slow. For an array of size n, there are 2^n possible combinations. For n=6, this is ok, for n=100, you will have to wait forever.

So if you are after a more efficient algorithm, I suggest you try a recursive approach. The subsets of a set of elements a1,...a_n can be divided into the ones containing a_n and those not containing a_n. Thus the subsets with a specific sum s are formed by

  • the subsets of a1,...a_(n-1) summing up to s
  • the subsets of a1,...a_(n-1) summing up to s - a_n, combined with the element a_n

This recursive process can be stopped when s becomes 0 or negative, or the total sum of the remaining a1,...a_k elements becomes less than s, or when s is greater 0, but the smallest element a_1 is greater than s.

I would expect this recursive approach to be much faster for bigger arrays.

  • To the an anonymous downvoter: if you tell me what you don't like, maybe I have a chance to improve my answer? – Doc Brown Sep 18 '14 at 10:47
1

What could be an efficient logic to solve this problem?

There aren't any. Even the first part of your question, "Given a number X, find a subset that sums to it", is NP-Complete. If you could find an efficient algorithm to solve this problem, you'd be in line for a Nobel prize.

  • The general meaning of "efficient" in common speech is not always "polynomial time", that's only the special viewpoint from the theory of algorithm complexity. I have my doubts that this is what the OP asks for. – Doc Brown Sep 18 '14 at 10:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.