Finding all the subsets in an array of integers that sum to a given target

Question

Problem Statement:

Given an Array if ints, Find out all the subsets in the Array that sum to a given target value.

Example:

If the input array is:

{1, 3, 2, 5, 4, 9} with target as 9

The resulting subsets are:

135
324
9
54

Below is my implementation in Java. Please free to review in terms of time, space complexity, style etc and a more efficient solution is welcome.

 import java.util.HashSet;
 /**
 * Created by anirudh on 12/5/15.
 */
 public class FindSubsetsThatSumToATarget {
 /**
 * The collection for storing the unique sets that sum to a target.
 */
 public static HashSet<String> allSubsets = new HashSet<>();
 /**
 * The method for finding the subsets that sum to a target.
 *
 * @param input The input array to be processed for subset with particular sum
 * @param target The target sum we are looking for
 * @param ramp The Temporary String to be beefed up during recursive iterations(By default value an empty String)
 * @param index The index used to traverse the array during recursive calls
 */
 private void FindTargetSumSubsets(int[] input, int target, String ramp, int index) {
 if(index > (input.length - 1)) {
 if(getSum(ramp) == target) {
 allSubsets.add(ramp);
 }
 return;
 }
 //First recursive call going ahead selecting the int at the currenct index value
 FindTargetSumSubsets(input, target, ramp + input[index], index + 1);
 //Second recursive call going ahead WITHOUT selecting the int at the currenct index value
 FindTargetSumSubsets(input, target, ramp, index + 1);
 }
 /**
 * A helper Method for calculating the sum from a string of integers
 *
 * @param intString the string subset
 * @return the sum of the string subset
 */
 private static int getSum(String intString) {
 int sum = 0;
 for (int i = 0; i < intString.length(); i++) {
 sum += Integer.parseInt(intString.substring(i, i + 1));
 }
 return sum;
 }
 /**
 * Cracking it up here : )
 *
 * @param args command line arguments.
 */
 public static void main(String[] args) {
 int [] n = {1, 3, 2, 5, 4, 9};
 new FindSubsetsThatSumToATarget().FindTargetSumSubsets(n, 9, "", 0);
 for (String str: allSubsets) {
 System.out.println(str);
 }
 }
}

I have some across a problem with the above implementation that in case of repeated values in the input array I am getting duplicate permutes of sets that sum to a given target.

E.g.: In input is:

int [] n = {2, 3, 2};

The resulting sets generated are:

32
23

Which in the given context are actually the same.

Answer 1

Violations of general good practices

• Using String.substring to extract single characters is odd. Use String.charAt instead next time
• Parsing single character strings using Integer.parseInt is odd. Use String.charAt(index) - '0' instead
• allSubsets should be declared as Set instead of HashSet (use interface types instead of implementations)
• Method names should be camelCase
• No need to write JavaDoc for private methods, simple comments are good enough, if needed at all

Strange way to collect integers

The way you collect integers in a String is strange in many ways:

• The program will not work for numbers> 9
• Appending digits to a string one by one, and then finally parsing them from the string one by one is strange.

You could use a Set instead. Sure, maybe it seems a bit strange and inefficient to clone the set in each recursive call, but I still think it would be better. It would also solve the problem you found, with the duplicate sequences in the results. Probably there is an even better way, but I have no more time now.

Strange static and non-static variables

allSubsets is static, but input and target are not. It would make more sense to either make all of these static, or none of them.

Not suggested implementation

I can't say I suggest this implementation, but it solves some issues with yours:

private void find(int[] input, int target, Set<Integer> ramp, int index) {
 if (index > input.length - 1) {
 if (getSum(ramp) == target) {
 allSubsets.add(toString(ramp));
 }
 return;
 }
 find(input, target, updatedSet(ramp, input[index]), index + 1);
 find(input, target, ramp, index + 1);
}
private Set<Integer> updatedSet(Set<Integer> ramp, int integer) {
 Set<Integer> updated = new HashSet<Integer>();
 updated.addAll(ramp);
 updated.add(integer);
 return updated;
}
private String toString(Set<Integer> ramp) {
 StringBuilder builder = new StringBuilder();
 for (Integer integer : ramp) {
 builder.append(integer);
 }
 return builder.toString();
}
private static int getSum(Set<Integer> integers) {
 int sum = 0;
 for (Integer integer : integers) {
 sum += integer;
 }
 return sum;
}

• Anirudh: The program will not work for numbers > 9? Please explain how it will not.
• Anirudh: Appending digits to a string one by one, and then finally parsing them from the string one by one is strange? Do you have an alternate approach that could replace this?
• janos: Since you treat all numbers as single digits, for input { 49, 51 } and target 100 the program gives no matches
• janos: An alternative that could replace this, work with numbers > 9, and eliminate your problem with duplicate sets, is to collect the numbers in a Set instead of a String, as I already explained in my review
• janos: I added the alternative implementation using a Set, but it's still ugly, so I can't say I recommend it.

Answer 2

@janos has covered a bunch of my concerns, except the algorithm you use.

I like the recursion, it makes sense, but I would make it a whole lot more efficient by doing two things....

1. sort the data first
2. recurse applying large values first, using binary searches as you go, if needed.

This way you can reduce the number of values in the set as you get close to the end.

Taking on most of the advice from janos, and applying the above, I would get something like:

private static Collection<int[]> findTargetSubSets(int[] n, int target) {
 int[] data = IntStream.of(n).sorted().toArray();
 List<int[]> results = new ArrayList<>();
 int[] partial = new int[data.length];
 recurseFor(data, data.length, partial, 0, target, results);
 return results;
}
private static void recurseFor(final int[] data, final int limit, final int[] partial, 
 final int psize, final int target, final List<int[]> results) {
 if (target == 0) {
 // found exact match.
 results.add(Arrays.copyOf(partial, psize));
 return;
 }
 if (limit == 0 || target < 0) {
 return;
 }
 int pos = Arrays.binarySearch(data, 0, limit, target);
 if (pos < 0) {
 pos = -pos - 1;
 pos--;
 }
 for (int i = 0; i <= pos; i++) {
 partial[psize] = data[i];
 recurseFor(data, i, partial, psize + 1, target - data[i], results);
 }
}

• Anirudh: IntStream ...Using Java 8?
• rolfl: @Anirudh - yeah... it crept in. It saves having to take an explicit copy of the array, and then sorting it with Arrays.sort(data)....
• Anirudh: Good to know but I am still not on Java 8 yet.
• Clement: Will this work if data is a float[] instead of int[]? I would think so. However how would you make this work if data contains negative numbers?
• Clement: Also is it necessary to do a binary search on each call? I would think it would be enough to loop all the way to limit but break the loop if the target - data[i] < 0