Лучший подход к подгонке чисел

Question

У меня есть следующий набор целых чисел {2,9,4,1,8}. Мне нужно разбить это множество на два подмножества, так что сумма множеств будет равна 14 и 10 соответственно. В моем примере ответ {2,4,8} и {9,1}. Я не ищу никакого кода. Я уверен, что для решения этой проблемы должен быть стандартный алгоритм. Поскольку я не был успешным в поиске в Google и узнал об этом, я отправил свой запрос здесь. Итак, какой будет лучший способ подойти к этой проблеме?

Моя попытка была, как это ...

public class Test { 
    public static void main(String[] args) { 
     int[] input = {2, 9, 4, 1, 8}; 
     int target = 14; 
     Stack<Integer> stack = new Stack<>(); 
     for (int i = 0; i < input.length; i++) { 
      stack.add(input[i]); 
      for (int j = i+1;j<input.length;j++) { 

       int sum = sumInStack(stack); 

       if (sum < target) { 
        stack.add(input[j]); 
        continue; 
       } 

       if (target == sum) { 
        System.out.println("Eureka"); 
       } 

       stack.remove(input[i]); 
      } 

     } 
    } 

    private static int sumInStack(Stack<Integer> stack) { 
     int sum = 0; 
     for (Integer integer : stack) { 
      sum+=integer; 
     } 
     return sum; 
    } 
} 

Я знаю, что этот подход не является даже близко решить проблему

Answer 1

Мне нужно разделить этот набор на два подмножества так, чтобы сумма из наборов результатов в 14 и 10 соответственно.

Если подмножества должны быть суммированы с определенными значениями, то лучше иметь в виду, что сумма всего набора является суммой этих значений, то есть 14 + 10 = 24 в вашем примере. Если вам нужно найти только два подмножества, то проблема не очень сложная - найдите любое подмножество, которое суммируется с одним из этих значений, а остальные элементы набора должны суммироваться с другим значением.

Для примера набор вы дали, {2,9,4,1,8}, вы сказали, что ответ {9,1}, {2,4,8}, но обратите внимание, что это не единственный ответ; есть также {2,8}, {9,4,1}.