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

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 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++)

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 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 updatedSet(Set ramp, int integer) {
    Set updated = new HashSet();
    updated.addAll(ramp);
    updated.add(integer);
    return updated;
}

private String toString(Set ramp) {
    StringBuilder builder = new StringBuilder();
    for (Integer integer : ramp) {
        builder.append(integer);
    }
    return builder.toString();
}

private static int getSum(Set integers) {
    int sum = 0;
    for (Integer integer : integers) {
        sum += integer;
    }
    return sum;
}

StackExchange Code Review Q#90670, answer score: 4