title: How to improve this algorithm for run-time efficiency?
body: <p>I recently had an assignment in my algorithms class. The problem statement is given below:</p>
  
  <blockquote>
    <p>Write and briefly explain the following C++ function: <code>int Sum (int *nums, int len);</code> that accepts an integer array, nums, containing len > 0 positive integers, and returns the sum closest to 330 that was found by adding up to three integers in the array (where each element of the array can only be included once in the sum).
    For example, if [nums] contains [10 100 200 2] and len==4, the function returns
    310=200+100+10. If [nums] contains [10 100 230 2] and len==4, the function returns 330=100+230.</p>
  </blockquote>
  
  <p>My attempt at the code:</p>
  
  <pre><code>#include &lt;iostream&gt;
  #include &lt;limits.h&gt;
  #include &lt;cmath&gt;
  #include &lt;climits&gt;
  using namespace std;
  
  /*
   * Description: function to find the sum closed to 330 by adding up
   *              to 3 integers
   * Arguments  : nums - integer array
   *              len  - length of integer array
   * Return     : sum closest to 330
   */
  int Sum (int *nums, int len)
  {
      const int number = 330;
      /* variable to store sum closest to 330 */
      int closest_sum = 0;
      /* variable to store difference of sum from 330 */
      int diff = INT_MAX;
      /* iterate over the integer array to find the sum closest to 330 */
      for(int i = 0; i &lt; len; i++)
      {
          /* temporary variable to hold sum of integers */
          int sum = 0;
          /* set first of 3 numbers as the sum */
          sum = nums[i];
          /* if the first number is equal to 330, no need to move forward; */
          /* return 330 */
          if(abs(number - sum) == 0) return number;
          /* compare the absolute difference of sum and 330 with previous */
          /* difference */
          if(abs(number - sum) &lt; diff)
          {
              /* if current difference is less than previous difference, */
              /* update diff and set closest sum to current sum */
              diff = abs(number - sum);
              closest_sum = sum;
          }
          /* include the second of 3 numbers */
          for(int j = i + 1; j &lt; len; j++)
          {
              /* set sum as the addition of the first 2 numbers */
              sum = nums[i] + nums[j];
              /* if the sum is equal to 330, no need to move forward; */
              /* return 330 */
              if(abs(number - sum) == 0) return number;
              /* compare the absolute difference of sum and 330 with previous */
              /* difference */
              if(abs(number - sum) &lt; diff)
              {
                  /* if current difference is less than previous difference, */
                  /* update diff and set closest sum to current sum */
                  diff = abs(number - sum);
                  closest_sum = sum;
              }
              /* include the third of 3 numbers */
              for(int k = j + 1; k &lt; len; k++)
              {
                  /* set sum as the addition of the 3 numbers */
                  sum = nums[i] + nums[j] + nums[k];
                  /* if the sum is equal to 330, no need to move forward; */
                  /* return 330 */
                  if(abs(number - sum) == 0) return number;
                  /* compare the absolute difference of sum and 330 with */
                  /* previous difference */
                  if(abs(number - sum) &lt; diff)
                  {
                      /* if current difference is less than previous */
                      /* difference, update diff and set closest sum to current */
                      /* sum */
                      diff = abs(number - sum);
                      closest_sum = sum;
                  }
              }
          }
      }
      /* return closest sum to 330 */
      return closest_sum;
  }
  
  int main() {
      const int len = 6;
      int arr[len] = {300, 320, 310, 500, 5, 330};
      cout &lt;&lt; "Closest to 330:\t" &lt;&lt; Sum(arr, len) &lt;&lt; endl;
      return 0;
  }
  </code></pre>
  
  <p>The code works correctly and passed all test cases that the grader used. However, part of the marks were related to the efficiency of the code. I lost points because the run-time of the code is ϴ(n^3) (because of the three nested <code>for</code> loops).</p>
  
  <p>My question is: how can this algorithm be improved to be more efficient i.e. with a run-time less than ϴ(n^3)?</p>
  
  <p>EDIT: Just to make it clear, up until the time when this assignment was due, we had only studied arrays/vectors, asymptotic notation, recursion/recurrence time in class. I am pretty sure we were not expected to use heaps, binary search (which, in fact, we will be studying next week), sorting algorithms etc. <strong>Also</strong>, please notice that the question says <strong>up to three integers</strong>, i.e. the closest sum to 330 can be made up of 1 number, 2 numbers or 3 numbers. I have to take in to account all these possibilities.</p>