I am printing subsets from an array whose sum has been specified, while avoiding duplicates.
I think there may be improvements, potentially on how using map
is bad idea, or how can I avoid map
to filter the duplicates.
Additionally, in my code I want to reverse the sort order of an int
array using streams which is asked over here, are there any alternatives rather than sorting and reversing the array?
public class FindSubSetArray {
private static final int TARGET_SUM = 24;
private static Map<String,Integer> subSet = new HashMap<>();
private static int count = 0;
public static void main(String[] args) {
int[] array= {2, 5, 1, 2, 4, 1, 6, 5, 2, 2};
Arrays.sort(array);
findSubset(array, 0, 0, "");
subSet.keySet().stream().forEach(System.out::println);
}
public static void findSubset(int[] array, int index, int current, String subSetString) {
if (current > TARGET_SUM || array.length < index) return;
for (int i = index; i < array.length; i++) {
int presentSum = current + array[i];
if (presentSum == TARGET_SUM) {
// System.out.println(subSetString + " " + array[i]);
subSet.put(subSetString + " " + array[i], count++);
} else {
findSubset(array, i + 1, presentSum, subSetString + " " + array[i]);
}
}
}
}
Arrays.sort()&reverse
to be faster for arrays not almost sorted) You not only exclude equal sequences of numbers, but overlapping ones, too - intentionally? Check what happens after the if (==)put()
else recursive call. (subSet makes me think of "no regard to position" or what is called (non-contiguous) subsequence - use slice or subArray?) – greybeard Jan 23 at 15:06