Recursion Backtracking

Printable View

• 03-28-2011, 12:02 PM
6thDAY
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

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);         } }```
• 03-28-2011, 05:06 PM
lovelesh
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.

Using pop simply removes the element from top of stack, which will not help your cause.