Сумма подмножества с положительными и отрицательными целыми числами

Question

Я должен реализовать вариант задачи суммы подмножеств, мой вклад будет положительным и отрицательным десятичным, также мне нужно будет знать подмножество, зная, что, к сожалению, существует, этого недостаточно.

Я пробовал алгоритмы, найденные в Википедии, но я не могу заставить их работать с отрицательными числами, а также я не могу найти способ получить подмножество, если оно существует.

Может ли кто-нибудь указать мне, где я мог бы найти псевдокод, документацию или реализацию для этого алгоритма.

Answer 1

Я написал код на Java, он проверяет все возможности

import java.util.*;

public class StackOverFlow {

    public static <T> Set<Set<T>> powerSet(Set<T> originalSet) {
        Set<Set<T>> sets = new HashSet<Set<T>>();
        if (originalSet.isEmpty()) {
            sets.add(new HashSet<T>());
            return sets;
        }
        List<T> list = new ArrayList<T>(originalSet);
        T head = list.get(0);
        Set<T> rest = new HashSet<T>(list.subList(1, list.size())); 
        for (Set<T> set : powerSet(rest)) {
            Set<T> newSet = new HashSet<T>();
            newSet.add(head);
            newSet.addAll(set);
            sets.add(newSet);
            sets.add(set);
        }       
        return sets;
    }

    public static int sumSet(Set<Integer> set){
        int sum =0;
        for (Integer s : set) {
            sum += s;
        }
        return sum;     
    }

    public static void main(String[] args) {
         Set<Integer> mySet = new HashSet<Integer>();
         mySet.add(-1);
         mySet.add(2);
         mySet.add(3);

         int mySum = 4;
         for (Set<Integer> s : powerSet(mySet)) {
             if(mySum == sumSet(s))
                 System.out.println(s + " = " + sumSet(s));
         }
    }
}

Я надеюсь, что это помогает