Generating partitions in Java

Question

I am given an integer (lets call it x) and I need to generate an array of arrays, where each subarray is a list of elements which are one of a given set of integers, and the sum of all of the elements of each subarray is x. The array of arrays needs to contain all possible distinct subarrays of this form.

For example, if x is 3 and the list of possible elements is {1, 2}, I'm looking to generate {{1, 2}, {2, 1}}.

What would be the best way to go about doing this (in pseudocode or Java)? Is this 2D array the best way to store this type of data? I couldn't think of anything better, but I'm guessing there is something out there.

Answer 1

Since you don't know the size of the "subarrays," I suggest you use one of the collections from Java such as ArrayList<E>.

Answer 2

For the storage, you probably want a LinkedList of HashSets:

LinkedList<HashSet<Integer>> l;

For the problem: This is the SubSet problem, which is NP-Complete, so I don't think there's a known, fast way to do it. I haven't taken any optimization theory, so the best I could do is to just search through the powerset of your input and see if any of their sums match the output.