title: Finding the largest sum of integers in a list less than a given value (code tracing)
body: <p>Had this problem in a review guide given by CS professor. I ended up solving the problem relatively naively by computing all possible sums of all integers in the list via recursive backtracking in a helper, storing these in a new list, then iterating through that list to find the max sum less than the given number.</p>
  
  <p>We were given the instructor's far more eloquent solution, but I'm having a lot of trouble dissecting it. Hopefully this is an acceptable place to ask for help breaking down what's going on (if not, apologies).</p>
  
  <pre><code>private static int largestSum(List&lt;Integer&gt; list, int n) {
      if (list.isEmpty()) {
          return 0;
      } else {
          int choice = list.get(0);
          list.remove(0);
          // Don't include choice in final sum
          int largest = sumHelper(list, n);
          if (choice &lt; n) {
              // Include choice in final sum
              int included = choice + sumHelper(list, n - choice);
              // Use whichever result is bigger
              largest = Math.max(largest, included);
          }
          // Return list to original state
          list.add(0, choice);
          return largest;
          }
  }
  </code></pre>
  
  <p>I understand the base case (we're iterating through the list by popping off the first element and recursing on the remainder, so when we hit the base case, we stop recursing and don't want to add anything hence the zero; it also addresses empty list). However, I'm still super unclear about the recursive case. I've stared at the code and tried to trace it for a while now, but wrapping my head around the recursion is proving very difficult. Can someone walk me through it?</p>