title: Given a list of numbers and a number k, return whether any two numbers from the list add up to k
body: <p>This question was asked in the Google programming interview. I thought of two approaches for the same:</p>
  
  <ol>
  <li><p>Find all the subsequences of length. While doing so compute the sum and of the two elements and check if it is equal to k. If ye, print Yes, else keep searching. This is a brute Force approach.</p></li>
  <li><p>Sort the array in non-decreasing order. Then start traversing the array from its right end. Say we have the sorted array,  {3,5,7,10} and we want the sum to be 17. We will start from element 10, index=3, let's denote the index with 'j'. Then include the current element and compute required_sum= sum - current_element. After that, we can perform a binary or ternary search in array[0- (j-1)] to find if there is an element whose value is equal to the required_sum. If we find such an element, we can break as we have found a subsequence of length 2 whose sum is the given sum. If we don't find any such element, then decrease the index of j and repeat the above-mentioned steps for resulting subarray of length= length-1 i.e. by excluding the element at index 3 in this case. </p></li>
  </ol>
  
  <p>Here we have considered that array could have negative as well as positive integers.</p>
  
  <p>Can you suggest a better solution than this? A DP solution maybe? A solution that can further reduce it's time complexity.</p>