Results 1 to 2 of 2
  1. #1
    6thDAY is offline Member
    Join Date
    Aug 2010
    Posts
    8
    Rep Power
    0

    Default 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. #2
    lovelesh is offline Senior Member
    Join Date
    Nov 2010
    Location
    Delhi
    Posts
    135
    Blog Entries
    1
    Rep Power
    0

    Smile

    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.

Similar Threads

  1. Backtracking
    By pali185 in forum New To Java
    Replies: 2
    Last Post: 12-17-2010, 01:08 PM
  2. Replies: 6
    Last Post: 12-08-2010, 12:39 AM
  3. need help with backtracking
    By Dumisan in forum Advanced Java
    Replies: 9
    Last Post: 02-17-2010, 01:02 PM
  4. recursion and tail-recursion differences
    By OptimusPrime in forum New To Java
    Replies: 2
    Last Post: 12-28-2009, 06:26 PM
  5. Recursion
    By Mika in forum New To Java
    Replies: 5
    Last Post: 01-04-2009, 01:13 AM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •