Sum-subset with a fixed subset size

by

For k=4, space complexity O(n), time complexity O(n2 * log(n))

Sort the array. Starting from 2 smallest and 2 largest elements, calculate all lesser sums of 2 elements (a[i] + a[j]) in the non-decreasing order and all greater sums of 2 elements (a[k] + a[l]) in the non-increasing order. Increase lesser sum if total sum is less than zero, decrease greater one if total sum is greater than zero, stop when total sum is zero (success) or a[i] + a[j] > a[k] + a[l] (failure).

The trick is to iterate through all the indexes i and j in such a way, that (a[i] + a[j]) will never decrease. And for k and l, (a[k] + a[l]) should never increase. A priority queue helps to do this:

  1. Put key=(a[i] + a[j]), value=(i = 0, j = 1) to priority queue.
  2. Pop (sum, i, j) from priority queue.
  3. Use sum in the above algorithm.
  4. Put (a[i+1] + a[j]), i+1, j and (a[i] + a[j+1]), i, j+1 to priority queue only if these elements were not already used. To keep track of used elements, maintain an array of maximal used ‘j’ for each ‘i’. It is enough to use only values for ‘j’, that are greater, than ‘i’.
  5. Continue from step 2.

For k>4

If space complexity is limited to O(n), I cannot find anything better, than use brute force for k-4 values and the above algorithm for the remaining 4 values. Time complexity O(n(k-2) * log(n)).

For very large k integer linear programming may give some improvement.

Update

If n is very large (on the same order as maximum integer value), it is possible to implement O(1) priority queue, improving complexities to O(n2) and O(n(k-2)).

If n >= k * INT_MAX, different algorithm with O(n) space complexity is possible. Precalculate a bitset for all possible sums of k/2 values. And use it to check sums of other k/2 values. Time complexity is O(n(ceil(k/2))).

More Related Contents:

  1. Custom Weighted Scale [closed]
  2. Finding all possible combinations of numbers to reach a given sum
  3. What is tail call optimization?
  4. How to convert floats to human-readable fractions?
  5. Is there an efficient way to generate N random integers in a range that have a given sum or average?
  6. Why is quicksort better than mergesort?
  7. Data structures for loaded dice?
  8. Pseudorandom Number Generator – Exponential Distribution
  9. Natural Sorting algorithm
  10. What is the fastest integer factorization algorithm?
  11. Is there an algorithm for color mixing that works like mixing real colors?
  12. How to read values from numbers written as words?
  13. Find the missing and duplicate elements in an array in linear time and constant space
  14. Function for creating color wheels [closed]
  15. Efficiently reverse the order of the words (not characters) in an array of characters
  16. What algorithm to use to determine minimum number of actions required to get the system to “Zero” state?
  17. What is a bubble sort good for? [closed]
  18. How do I find a factorial? [closed]
  19. Compute rank of a combination?
  20. Efficiently selecting a set of random elements from a linked list
  21. Skip List vs. Binary Search Tree
  22. reconstructing a tree from its preorder and postorder lists
  23. Best way of calculating n choose k?
  24. Generating shuffled range using a PRNG rather than shuffling
  25. Randomly choosing from a list with weighted probabilities
  26. Path generation for non-intersecting disc movement on a plane
  27. Algorithm for permutations of operators and operands
  28. Tournament bracket placement algorithm
  29. How to convert decimal fractions to hexadecimal fractions?
  30. Best algorithm for matching colours.

Leave a Comment