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&lt;String&gt; allSubsets = new HashSet&lt;&gt;();

    /**
     * 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 &gt; (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 &lt; 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.
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&lt;Integer&gt; ramp, int index) {
    if (index &gt; 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&lt;Integer&gt; updatedSet(Set&lt;Integer&gt; ramp, int integer) {
    Set&lt;Integer&gt; updated = new HashSet&lt;Integer&gt;();
    updated.addAll(ramp);
    updated.add(integer);
    return updated;
}

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

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