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].
4
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 tos - the subsets of
a1,...a_(n-1)summing up tos - a_n, combined with the elementa_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.
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.
1