Since no-one else has made an attempt, I might as well throw in at least a partial solution. As I pointed out in an earlier comment, this problem is a variant of the subset sum problem and I have relied heavily on documented approaches to that problem in developing this solution.
We're trying to write a function subsetsWithSum(A, k, s) that computes all the k-length subsets of A that sum to s. This problem lends itself to a recursive solution in two ways:
- The solution of subsetsWithSum(x1 ... xn, k, s) can be found by computing subsetsWithSum(x2 ... xn, k, s) and adding all the valid subsets (if any) that include x1; and
- All the valid subsets that include element xi can be found by computing subsetsWithSum(A - xi, k-1, s-xi) and adding xi to each subset (if any) that results.
The base case for the recursion occurs when k is 1, in which case the solution to subsetsWithSum(A, 1, s) is the set of all single element subsets where that element is equal to s.
So a first stab at a solution would be
/**
* Return all k-length subsets of A starting at offset o that sum to s.
* @param A - an unordered list of integers.
* @param k - the length of the subsets to find.
* @param s - the sum of the subsets to find.
* @param o - the offset in A at which to search.
* @return A list of k-length subsets of A that sum to s.
*/
public static List<List<Integer>> subsetsWithSum(
List<Integer> A,
int k,
int s,
int o)
{
List<List<Integer>> results = new LinkedList<List<Integer>>();
if (k == 1)
{
if (A.get(o) == s)
results.add(Arrays.asList(o));
}
else
{
for (List<Integer> sub : subsetsWithSum(A, k-1, s-A.get(o), o+1))
{
List<Integer> newSub = new LinkedList<Integer>(sub);
newSub.add(0, o);
results.add(0, newSub);
}
}
if (o < A.size() - k)
results.addAll(subsetsWithSum(A, k, s, o+1));
return results;
}
Now, notice that this solution will often call subsetsWithSum(...) with the same set of arguments that it has been called with before. Hence, subsetsWithSum is just begging to be memoized.
To memoize the function, I've put the arguments k, s and o into a three element list which will be the key to a map from these arguments to a result computed earlier (if there is one):
public static List<List<Integer>> subsetsWithSum(
List<Integer> A,
List<Integer> args,
Map<List<Integer>, List<List<Integer>>> cache)
{
if (cache.containsKey(args))
return cache.get(args);
int k = args.get(0), s = args.get(1), o = args.get(2);
List<List<Integer>> results = new LinkedList<List<Integer>>();
if (k == 1)
{
if (A.get(o) == s)
results.add(Arrays.asList(o));
}
else
{
List<Integer> newArgs = Arrays.asList(k-1, s-A.get(o), o+1);
for (List<Integer> sub : subsetsWithSum(A, newArgs, cache))
{
List<Integer> newSub = new LinkedList<Integer>(sub);
newSub.add(0, o);
results.add(0, newSub);
}
}
if (o < A.size() - k)
results.addAll(subsetsWithSum(A, Arrays.asList(k, s, o+1), cache));
cache.put(args, results);
return results;
}
To use the subsetsWithSum function to compute all the k-length subsets that sum to zero, one can use the following function:
public static List<List<Integer>> subsetsWithZeroSum(List<Integer> A, int k)
{
Map<List<Integer>, List<List<Integer>>> cache =
new HashMap<List<Integer>, List<List<Integer>>> ();
return subsetsWithSum(A, Arrays.asList(k, 0, 0), cache);
}
Regrettably my complexity calculating skills are a bit (read: very) rusty, so hopefully someone else can help us compute the time complexity of this solution, but it should be an improvement on the brute-force approach.
Edit: Just for clarity, note that the first solution above should be equivalent in time complexity to a brute-force approach. Memoizing the function should help in many cases, but in the worst case the cache will never contain a useful result and the time complexity will then be the same as the first solution. Note also that the subset-sum problem is NP-complete meaning that any solution has an exponential time complexity. End Edit.
Just for completeness, I tested this with:
public static void main(String[] args) {
List<Integer> data = Arrays.asList(9, 1, -3, -7, 5, -11);
for (List<Integer> sub : subsetsWithZeroSum(data, 4))
{
for (int i : sub)
{
System.out.print(data.get(i));
System.out.print(" ");
}
System.out.println();
}
}
and it printed:
9 -3 5 -11
9 1 -3 -7
Does anyone know a solution that would satisfy the new constraints?– Cyclone