Minimal non-contiguous sequence of exactly k elements

Question

The problem I'm having can be reduced to:

Given an array of N positive numbers, find the non-contiguous sequence of exactly K elements with the minimal sum.

Ok-ish: report the sum only. Bonus: the picked elements can be identified (at least one set of indices, if many can realize the same sum).

(in layman terms: pick any K non-neighbouring elements from N values so that their sum is minimal)

Of course, 2*K <= N+1 (otherwise no solution is possible), the problem is insensitive to positive/negative (just shift the array values with the MIN=min(A...) then add back K*MIN to the answer).

What I got so far (the naive approach):

1. select K+2 indexes of the values closest to the minimum. I'm not sure about this, for K=2 this seems to be the required to cover all the particular cases, but I don't know if it is required/sufficient for K>2**
2. brute force the minimal sum from the values of indices resulted at prev step respecting the non-contiguity criterion - if I'm right and K+2 is enough, I can live brute-forcing a (K+1)*(K+2) solution space but, as I said. I'm not sure K+2 is enough for K>2 (if in fact 2*K points are necessary, then brute-forcing goes out of window - the binomial coefficient C(2*K, K) grows prohibitively fast)

Any clever idea of how this can be done with minimal time/space complexity?

** for K=2, a non-trivial example where 4 values closest to the absolute minimum are necessary to select the objective sum [4,1,0,1,4,3,4] - one cannot use the 0 value for building the minimal sum, as it breaks the non-contiguity criterion.

PS - if you feel like showing code snippets, C/C++ and/or Java will be appreciated, but any language with decent syntax or pseudo-code will do _{(I reckon "decent syntax" excludes Perl, doesn't it?)}

Answer 1

Let's assume input numbers are stored in array a[N]

Generic approach is DP: f(n, k) = min(f(n-1, k), f(n-2, k-1)+a[n])

It takes O(N*K) time and has 2 options:

• for lazy backtracking recursive solution O(N*K) space
• for O(K) space for forward cycle

In special case of big K there is another possibility:

• use recursive back-tracking
• instead of helper array of N*K size use map(n, map(k, pair(answer, list(answer indexes))))
• save answer and list of indexes for this answer
• instantly return MAX_INT if k>N/2

This way you'll have lower time than O(NK) for K~=N/2, something like O(Nlog(N)). It will increase up to O(N*log(N)Klog(K)) for small K, so decision between general approach or special case algorithm is important.