1. Member
Join Date
Aug 2010
Posts
8
Rep Power
0

## Recursion Backtracking

Hello, I have to do a program that involves reading in a bunch of integer numbers from a user. Then have the user enter a particular sum. Then I have to search the list to see what numbers add up to the sum using recursion.

I always hated recursion, conceptionually for me its difficult to grasp ahold off.

Anyways I have this code, but I am completely lost as to how to implement my searchSum() method. Can someone point me in the right direction? Thanks

Java Code:
public class SumUp
{

/**
* @param args
*/
public static void main(String[] args)
{
int numList = 0;
int numbers;
int result = 0;
int pickSum = 0;

Stack<Integer> yourNumbers = new Stack<Integer>();
Scanner keyboard = new Scanner(System.in);

System.out.println("Enter a list of whole numbers. Type -1 when done: ");

while (numList != -1)
{
numList = keyboard.nextInt();
yourNumbers.push(numList);
}
numbers = yourNumbers.pop(); //removes and excludes -1

System.out.println("Now pick a desired sum: ");
pickSum = keyboard.nextInt();

System.out.println(sumSearch(pickSum, yourNumbers));

int sizeOfList = yourNumbers.size();

for (int index = 0; index < sizeOfList; index++)
{
numbers = yourNumbers.pop();
result += numbers;
}

System.out.println("The sum is: " + result);

}

public static String sumSearch(int sum, Stack<Integer> numStack)
{
int last = numStack.pop();
int first = numStack.pop();

if (last == sum || first == sum)
{
return ("The subset of number(s) yielding the sum are " + last);
}
else
return sumSearch(sum, numStack);
}
}

2. Senior Member
Join Date
Nov 2010
Location
Delhi
Posts
135
Blog Entries
1
Rep Power
0
6thDAY:
You need to revisit the logic inside sumSearch method.

Don't use pop api of Stack, because you need not remove the element while trying to find the sum. Use peek() for this, as it is quite possible that first element might pair up with any element in the stack to get the desired sum.