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 9The 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.