0

I have a list of numbers and a target sum. The sum can be made from some of these numbers and sometimes cannot be made. Is there a way in Java or any other language to optimally/quickly find a subset of these numbers that could some up to a given target sum or if it's not possible to find the subset that gives the closest sum to the target sum?

For example, my current list of numbers has about 1000 numbers of 3-5 digits. And I have multiple target sums. For instance, 2'167'789 or 49'450. The target sum is usually 5-7 digits.

Right now, I have a basic recursive algorithm that goes through all of the possible combinations without doing any "smart" things. And thus, I usually either run out of memory or just wait hours to realise that something went wrong at the end.

If I can't make a sum from the numbers given, I need to pick numbers that will give me the closest sum to the target one.

This is the code I have:

public static void findAllPossibleLists(int goal, int currentSum, ArrayList<Integer> included, ArrayList<Integer> notIncluded, int startIndex) {
  for (int i = startIndex; i < notIncluded.size(); i++) {
    int currentNumber = notIncluded.get(i);

    // if equal to goal or it's the last item in the list (technically not precisely right thing to compare to...)
    if (currentSum + currentNumber == goal) {
      // save this result
      ArrayList<Integer> newResult = new ArrayList<>(included);
      newResult.add(currentNumber);
      allResults.add(newResult);
    } else if (currentSum + currentNumber < goal) {
      // continue
      ArrayList<Integer> newIncluded = new ArrayList<>(included);
      newIncluded.add(currentNumber);

      ArrayList<Integer> newNotIncluded = new ArrayList<>(notIncluded);
      newNotIncluded.remove(i);

      findAllPossibleLists(goal, currentSum + currentNumber, newIncluded, newNotIncluded, startIndex++);
    } else if (currentSum + currentNumber > goal) {
      // save the result without the last item found
      allResults.add(new ArrayList<>(included));
    }
  }
}

I run this using this initial call:

findAllPossibleLists(goal, 0, new ArrayList<>(), new ArrayList<>(numbers), 0);

where numbers is an array of given numbers.

Mark Rotteveel
  • 100,966
  • 191
  • 140
  • 197
Sam
  • 112
  • 1
  • 8
  • 2
    Sounds np-complete to me. So, try all combinations …. Sort the list first. – Thorbjørn Ravn Andersen Jul 10 '21 at 20:26
  • 2
    This should help - https://en.wikipedia.org/wiki/Subset_sum_problem – pablochan Jul 10 '21 at 20:31
  • 1
    Does this answer your question? [Subset Sum algorithm](https://stackoverflow.com/questions/4355955/subset-sum-algorithm) – risingStark Jul 12 '21 at 04:11
  • It looks like [knapsack problem](https://en.wikipedia.org/wiki/Knapsack_problem) to me. To solve it in a O(n) way you need to use more memory (an array that store in its `i`-th cell if the sum until `i` is reachable or not). Let me know if the knapsnak problem does fit your problem, I can make a bigger answer. – Doreapp Jul 14 '21 at 17:50

1 Answers1

0

This is an example of Subset Sum Problem. An example of a solution to it is provided at Geeksforgeeks.

Sam
  • 112
  • 1
  • 8