Share the post "Get Subset From Set That Sum To A Value Using Java"
This is beyond my intellect since I am just totally bad with Math so the only thing left for me to do was the scour the Internet to try and find if anyone posted a solution to getting a list of subset from a given set that sum up to a specific value.
I wanted it to be a simple static method but out of the possible solutions that I came across with, only the class made by user rolfl in the Code Review StackExchange website met my needs.
This class made it possible for me to use the class and loop through each set and see if any of those have numbers that sum up to the specific value that I want.
Here is the class.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 |
public class GetAllSubsetByStack { /** Set a value for target sum */ private int TARGET_SUM; private Stack<Integer> stack = new Stack<Integer>(); /** Store the sum of current elements stored in stack */ private int sumInStack = 0; private ArrayList<Stack<Integer>> subsets; public GetAllSubsetByStack(int sum) { TARGET_SUM = sum; } public void populateSubset(ArrayList<Integer> ai, int startIndex) { /* * Check if sum of elements stored in Stack is equal to the expected * target sum. * * If so, call print method to print the candidate satisfied result. */ if (sumInStack == TARGET_SUM) { print(stack); if (subsets == null) subsets = new ArrayList<Stack<Integer>>(); subsets.add(stack); } for (int currentIndex=startIndex; currentIndex<ai.size(); currentIndex++) { if (sumInStack + ai.get(currentIndex) <= TARGET_SUM) { stack.push(ai.get(currentIndex)); sumInStack += ai.get(currentIndex); /* * Make the currentIndex +1, and then use recursion to proceed * further. */ populateSubset(ai, currentIndex + 1); sumInStack -= (Integer) stack.pop(); } } } /** * Print satisfied result. i.e. 15 = 4+6+5 */ private void print(Stack<Integer> stack) { StringBuilder sb = new StringBuilder(); sb.append(TARGET_SUM).append(" = "); for (Integer i : stack) { sb.append(i).append("+"); } System.out.println(sb.deleteCharAt(sb.length() - 1).toString()); } public int getSubsetsSize() { return subsets == null ? 0 : subsets.size(); } public void reset() { stack.removeAllElements(); sumInStack = 0; } } |
To use the class. Do it like this:
|
1 2 3 |
GetAllSubsetByStack gasbs = new GetAllSubsetByStack(15); gasbs.populateSubset(dummy, 0); int totalsubset = gasbs.getSubsetsSize(); |
The example looks for subsets of a given set that sum up to the value 15. The dummy variable is an ArrayList of type Integer.
Then, if any subsets are found within the set, the totalsubset variable will have a value of more than 0.
You can modify the class to suit your requirements like getting the list of subsets by modifying the code in the print() method.
