From The Algorithm Design Manual Solution Wiki
Jump to navigation Jump to search

Here the main thing to notice is that we need a O() solution.
For various values of k,
k Solution Time Complexity
1 O()
2 O()
3 O()
4 O()

for k = 2 onwards
1. sort the array ( nlogn )
2. use k-1 loops for iterating over array, where ith loop starts from i-1 + 1 element of array, and then use binary search
for k = 3
for( i = 0; i < n; i++ )
for( j = i+1; j < n; j++ )

  1. now use binary search to find ( T - a[i] - a[j] ) from j+1 element to end of array

Another recursive solution

First, we note that an O() solution for exists, which is already within the required bounds. Now, for , we can do something like this:

sort S ascending;
CheckSumOfK(S, k, T); // defined below

// S must be aorted array of integers
function CheckSumOfK(S, k, T)
    if k <= 2:
        Use any method in the solution of ex 4.8 and return the result. This can be done in O(n) time because S is sorted.

    Initialize array A of n - 1 elements;
    for i from 0 to n - 1:
        k = 0
        // Collect in A all numbers in S but S[i]. Note that A will still be sorted.
        for j from 0 to n - 1:
            if i != j:
                A[k] = S[j];
                k = k + 1
        // If S[i] is included in the k integers that sum up to T, then there must
        // exactly (k - 1) integers in the rest of S (i.e., A) that sum to (T - S[i]).
        // We can find that out by calling ourselves recursively.
        if CheckSumOfK(A, k - 1, T - S[i]):
            return True
    return False


For each item in S, there is work done in assembling the array A, except at the recursive call, which completes in time. So, for each number in S, we have work, and since , each iteration of the outer loop takes work. Now since the outer loop goes on for at most iterations, we have a total runtime of .

A trick can be used to lower this runtime to by having the routines in this solution take an index to ignore when iterating in their inner loops. With this, we save the construction of A for every item, and then each iteration of the outer loop becomes (How? constant time recursive calls plus time spent in the calls), giving a total runtime of for elements in S.

Note that this cost includes the initial cost for sorting S. Also, this algorithm is always going to be for all . The exercise just states an upper bound.

Back to Chapter 4