Walrus Weights/Getting a combination in an array whose sum is closest 1000

Question

I've been working on this problem https://open.kattis.com/problems/walrusweights. I saw that someone else had asked about it here, but my approach to this problem is completely different.

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.

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:

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) < 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);
    }
}

with:

combination(0, nums, false, 0, 1000001); //limit of weights is 1000000

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.

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.

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?

Answer 1

A bit late, but I've answered this and will leave it here for others to see if they need to.

http://hastebin.com/etapohavud.cpp

I made a recursive method that traverses the array of numbers (which was previously sorted), only checking sums that could lead to the closest one, adding all possible ones to an ArrayList. It is sorted so I would not have to worry about finding a smaller number ahead, which could change the whole current sum that I am checking.

In short, I calculated all viable combinations that could end up being the closest to 1000 and then found the one closest to it.