JAVA/C++ Algorithum Write a program that solves the Subset Sum Problem for the f
ID: 3689759 • Letter: J
Question
JAVA/C++ Algorithum
Write a program that solves the Subset Sum Problem for the following sets:
Set A: {-7, -3, -2, 5, 8}
Set B: {6, 5, 3, 1, 8, 7, 2, 4, -2, -3}
For each set, record the start time and end time for the solution.
Modify your program to solve the Subset Sum Problem for Set C that includes a random number of integers (20 >= n <= 100), with each value ranging from -10 to 10. In other words, the size of the set will be a random number from 20 to 100 inclusive, with each element in the set being a random number from -10 to 10 inclusive.
Run the Subset Sum Problem 3 times for Set C and record the start and end time for the solution.
Note: Your code may not halt (i.e., welcome to the Halting Problem), so you should have a mechanism to end your code when this occurs.
Explanation / Answer
GetAllSubsetByStack class
public class GetAllSubsetByStack {
/** Set a value for target sum */
public static final int TARGET_SUM = 8;
private Stack<Integer> stack = new Stack<Integer>();
/** Store the sum of current elements stored in stack */
private int sumInStack = 0;
public void populateSubset(int[] data, int fromIndex, int endIndex) {
/*
* 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);
}
for (int currentIndex = fromIndex; currentIndex < endIndex; currentIndex++) {
if (sumInStack + data[currentIndex] <= TARGET_SUM) {
stack.push(data[currentIndex]);
sumInStack += data[currentIndex];
/*
* Make the currentIndex +1, and then use recursion to proceed
* further.
*/
populateSubset(data, currentIndex + 1, endIndex);
sumInStack -= (Integer) stack.pop();
}
}
}
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());
}
}
Main class
public class Main {
private static final int[] DATA = {6, 5, 3, 1, 8, 7, 2, 4, -2, -3}
public static void main(String[] args) {
GetAllSubsetByStack get = new GetAllSubsetByStack();
get.populateSubset(DATA, 0, DATA.length);
}
}
follow same code for SET A
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.