title: Walrus Weights/Getting a combination in an array whose sum is closest 1000
body: <p>I've been working on this problem <a href="https://open.kattis.com/problems/walrusweights" rel="nofollow">https://open.kattis.com/problems/walrusweights</a>. I saw that someone else had asked about it here, but my approach to this problem is completely different.</p>
  
  <p>In the problem, you must find a combination in an array that's sum is closest to 1000. Here's my solution, it works well under the time limit (0.26s, limit is 2s), however, after 31 test cases, it gives me wrong answer.</p>
  
  <p>In my program, I first read all the numbers and make it to an array size n + 1 (with a zero as the first number, I'll explain shortly), and then I call this method:</p>
  
  <pre><code>public static void combination(int index, boolean use, int currentSum, int closest){
      HS.add(currentSum);
      HS.add(closest);
      if(index == size){
          return;
      }
      if(use)
          currentSum += array[index];
      index++;
      if(currentSum == 0){ //would interfere with the if statement below, if it's 0, it will always be closer to 1000 
          combination(index, true, currentSum, closest);
          combination(index, false, currentSum, closest);
      }
      else{
          if(Math.abs(1000 - currentSum) &lt; Math.abs(1000 - closest)){//so, if the currentSum is closer to 1000 than the closest so far
              closest = currentSum; //this is now the closest one
          }
          else //otherwise, there's no point going on with further changes to this combination, it will never be closest
              return;
          combination(index, true, currentSum, closest);
          combination(index, false, currentSum, closest);
      }
  }
  </code></pre>
  
  <p>with:</p>
  
  <pre><code>combination(0, nums, false, 0, 1000001); //limit of weights is 1000000
  </code></pre>
  
  <p>In the combination method, the parameters are the index you're currently on, the array, whether you will be adding the current entry to the sum, the current sum, and the highest combination closest to 1000 so far.</p>
  
  <p>I made a method that once all of the combinations are done, it gets the one closest to 1000 but I'm positive that that works, and it's pretty simple so it's not worth showing, unless needed.</p>
  
  <p>Can anyone tell me what I'm doing wrong? Is the logic of the combination method incorrect, or is there an extra check or something of the sort I'm missing?</p>