set

[48T7M4Gy]

My algorithm above can be dramatically improved by stopping the summation process where the difference between any two consecutive summations is >= 2. The answer will be the first intermediate value. The algorithm is also improved by 'matrix summation' of all values below, but no including the diagonal.

[lastchance]

int array[] = {10,20,50,6,7,5,8,56,230,4,27,19};
19  <-- FIRST ... QED

The first number not expressible as a subset is definitely ... 1
(This is similar to the second example in Biwkina's link; also 19 is a member of the set, so can't be the answer.)

int array[] = {1,2,5,6,7,5,8,56,23,4,2,19};
16    <-- FIRST ... QED

16 = 1 + 2 + 5 + 8
Again, expressible as the sum of a subset. In fact, every number between 1 and 138 inclusive is expressible as the sum of a subset. The answer is 139.


In Biwkina's problem:
"unimaginable[sic] as the sum of the elements of any subset of the set."

[48T7M4Gy]

Well lastchance, I take your point that the problem definition says there can be more than two member subset involved in the summation which I failed to take into account.

So, 19 = 10 + 4 +5 doesn't provide an answer and the same can be said for 16 = 1 + 2 + 5 + 8 in the second one as you describe.

Maybe I need to review the knapsack problem as a possible avenue but fuck it, I'll move on.

Good luck with it though.

Cheers :)

[biwkina]

http://www.cplusplus.com/forum/beginner/204866/

any ideas?

[keskiverto]

The task seems to require two steps:
1. sort
2. linear search. O(n)


What is actually tested?

Can a student streamline a naive brute-force solution to be fast enough.
OR
Can the student figure out a mathematical solution.

[lastchance]

Still intrigued by Biwkina's subset-non-sum problem. (Sorry - I really ought to move on!)

Took a bit of exploration on relevant google search terms, but I found this item
http://algorithms.tutorialhorizon.com/minimum-number-that-cannot-be-formed-by-any-subset-of-an-array/
(which I'm still trying to understand).

[keskiverto]

@lastchance:
Lets have a set S that produces all consecutive integers from 1 to sum(S) as subset-sums, just like the example above that had 139 as the answer. The 138 was the sum of all set members, wasn't it? The least non-sum is thus sum(S)+1.

Lets add a new value 'foo' to the set, creating S'. Our set is sorted, so the foo >= max(S).

Range from 1 to sum(S) has sum(S) unique values. By adding the foo to each sum we get a consecutive range from foo+1 to foo+sum(S). The foo alone is a subset too, so the range is actually from foo to foo+sum(S).

If the foo is at most sum(S)+1, then the new set S' is from 1 to sum(S'), consecutive. The least non-sum is sum(S')+1.

However, if the foo is more than sum(S)+1, then the subset sums of S' is two disjoint ranges: from 1 to sum(S) and from foo to sum(S'). In that case sum(S) < sum(S)+1 < foo and the sum(S)+1 remains the smallest non-sum.

[lastchance]

Thanks Keskiverto,

I almost spotted the pattern and particularly the gaps/disjoint ranges when I wrote in my code:

         if ( j < item && !sumData[j] )                    // if data is sorted, this will never be a sum, so can stop
         {
            cout << "Answer: " << j;
            exit( 0 );
         }

... but I never quite realised it and ended up ticking off a whole boolean array of values when I didn't need to. I should have been trying it out on paper - I might have spotted the algorithm.

Some of the other algorithms on that site look very useful.

The set of values with 138 as sum and 139 as first non-subset sum was actually a fluke!