Генерация разделов в Java

Question

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

Например, если x равен 3 и список возможных элементов равен {1, 2}, я собираюсь сгенерировать {{1, 2}, {2, 1}}.

Каков наилучший способ сделать это (в псевдокоде или на Java)? Является ли этот 2D-массив лучшим способом для хранения данных такого типа? Я не мог придумать ничего лучшего, но, думаю, что-то там есть.

Answer 1

Для хранилища вам, вероятно, нужен LinkedList из HashSets:

LinkedList<HashSet<Integer>> l;

Для проблемы: это проблема SubSet, которая является NP-Complete, поэтому я не думаю, что есть известный, быстрый способ сделать это. Я не взял никакой теории оптимизации, поэтому лучшее, что я мог сделать, - это просто просмотреть набор параметров питания вашего ввода и посмотреть, соответствует ли какая-либо из их сумм выводу.

Answer 2

Поскольку вы не знаете размер «подмассивов», я предлагаю вам использовать одну из коллекций из Java, например ArrayList<E>.