1) This problem was motivated by http://en.wikipedia.org/wiki/3SUM and http://rjlipton.wordpress.com/2014/08/13/our-three-body-problem/

Input: Given A Set S of integers  and D
Output: output a,b,c such that a+b+c=d , a,b,c are distinct and in S or no such numbers exit.

Idea: Make a < b < c
Algorithm:


Sort(s) // sort numbers in increasing order.

for i=0 to n-3  // indices go from 0 to n-1 in S. The highest index of a can be n-3
 {
  a = S[i]
  j=i+1
  k=n-1  // clever step burning the candle from both sides
  b = S[j]
  c = S[k]
  while (j < k) 
   {
     if (a+b+c == d) 
         return (a,b,c)
     if (a+b+c < d )
        j = j+1
        b = S[j]
     else
        k = k-1
        c = S[j]
    }

}
return (-1) // no solution exists

For each possible a (there are O(n) choices, b and c are found in O(n) steps - So the time complexity is O(n^2).

Think how will you modify the algorithm if distinctness is omitted.

Extra Credit:  This problem is known as Knapsack problem (we will study this problem using Dynamic Programming)
Answer; 2*16+4*17 = 100

This problem is motivated by the NPR Weekend Puzzle Segment. Please see http://www.npr.org/2014/08/17/340944712/is-there-an-echo-in-here towards the end.