Results 1 to 15 of 15
  1. #1
    Yakg is offline Member
    Join Date
    Dec 2010
    Posts
    59
    Rep Power
    0

    Default Clever glimpse needed with this recursion

    Hi, the following program should take two parameters (array[],int number)
    and checks if the given number could be returned by summing or subtracting the objects in from the array.
    Ex. if number is: 31 and the array {5,22,13,5,7,-4}.
    Returns true because 22+13-4=31 .

    My code isn't finish I just want to know if I'm doing too much or should I go on with this madness. It should be all recursive no loops.

    My idea: I wanted to sort the array first from large to small numbers and then
    take the largest and if larger find a negative value and if smaller keep adding.

    Java Code:
    public class Test2Q1{
        
        public static boolean cover (int [] values, int amount){
        if (values.length>1)
            cover (values,0,1,amount) ;
            return false;
        }
        
        private static boolean cover (int [] values, int i, int j, int amount){ //rearranger
            int key = values[j];
            i = j-1;
            if (i>-1 && values[i] < key){
                values[i+1] = values[i];
                cover (values,i=i-1,j,amount);
            }
            values [i+1] = key;
            if (j<values.length)
            cover (values,i,j++,amount);
            return cover(values,amount,0,0);
        }
        
        private static boolean cover (int [] values,int amount, int i,int neg){ //find negatives
            if ( i<values.length-1){
            if (values[i] >0) 
            cover (values,amount,i+1,neg);
            cover (values,amount,i+1,neg+1);
        }
        return cover (values,amount,neg,0,0);
    }
    // ----- phase 1. array rearranged and the neg values found. -----.
        
    // Start of phase 2.
        private static boolean cover (int [] values,int amount, int neg, int helper, int i){ //checks if == or <
           neg = (values.length)-neg;
           if (helper<amount) 
           helper += values[i];
            if (helper == amount) //base case
            return true;
            //------------------------------ok---!
            if (helper<amount)
            cover (values,amount,neg,helper,i+1); //continue as long as helper is < than the amount.
            //if >
            if (neg != values.length){ //if there are negative values.
                helper+=neg;
                if (helper>amount)
                 cover (values,amount,neg-1,helper,i);
                 //if <
    It's unfinished I know it's long but just a quick look would help.
    Your help is much appreciated thanks.

  2. #2
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,004
    Blog Entries
    7
    Rep Power
    20

    Default

    Quote Originally Posted by Yakg View Post
    Hi, the following program should take two parameters (array[],int number)
    and checks if the given number could be returned by summing or subtracting the objects in from the array.
    Ex. if number is: 31 and the array {5,22,13,5,7,-4}.
    Returns true because 22+13-4=31 .
    A simple question for you: if the target number would've been 17 is the method supposed to return true also? (22-5 == 17)

    kind regards,

    Jos
    cenosillicaphobia: the fear for an empty beer glass

  3. #3
    Yakg is offline Member
    Join Date
    Dec 2010
    Posts
    59
    Rep Power
    0

    Default Yes.

    If there is a solution true, if it can't be reached then, false.

    So what I'm planning to do is check for the next largest element each time
    and if can't find one eventually and the result is !=number, then false.

  4. #4
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,004
    Blog Entries
    7
    Rep Power
    20

    Default

    Quote Originally Posted by Yakg View Post
    If there is a solution true, if it can't be reached then, false.

    So what I'm planning to do is check for the next largest element each time
    and if can't find one eventually and the result is !=number, then false.
    If you are allowed to either add or subtract one of the numbers from the target number there's no need to sort those numbers in the array. Here's a bit of code that tries all combinations and tries to find the target number. Do with it what you want. The solve( ... ) method takes the following parameters:

    1) the array of numbers.
    2) the target number
    3) the index of numbers that can still be used.
    4) a list of the used numbers

    Java Code:
    import java.util.ArrayList;
    import java.util.List;
    
    public class T {
    
    	private static void solve(int[] a, int sum, int i, List<Integer> terms) {
    		if (sum == 0) {
    			System.out.println(terms);
    		}
    		else if (i < a.length){
    			solve(a, sum, i+1, terms);
    			terms.add(a[i]);
    			solve(a, sum-a[i], i+1, terms);
    			terms.remove(terms.size()-1);
    			terms.add(-a[i]);
    			solve(a, sum+a[i], i+1, terms);
    			terms.remove(terms.size()-1);
    		}
    	}
    	
    	public static void main(String[] args) {
    
    		int[] a = {5,22,13,5,7,-4};
    		solve(a, 31, 0, new ArrayList<Integer>());
    	}
    }
    kind regards,

    Jos
    cenosillicaphobia: the fear for an empty beer glass

  5. #5
    Yakg is offline Member
    Join Date
    Dec 2010
    Posts
    59
    Rep Power
    0

    Default Great but, I can't use the list

    could I use an array instead?
    I will check if it works.

  6. #6
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,004
    Blog Entries
    7
    Rep Power
    20

    Default

    Quote Originally Posted by Yakg View Post
    could I use an array instead?
    I will check if it works.
    Internally an ArrayList<Integer> also uses an ordinary array so you can do it too; beware that you have to implement the nasty details of keeping track how many elements in the array are used, resizing the array when needed etc. yourself. Using an ArrayList<Integer> is much easier. On second thought, I'd better used a Stack<Integer> in my code ...

    kind regards,

    Jos
    cenosillicaphobia: the fear for an empty beer glass

  7. #7
    Yakg is offline Member
    Join Date
    Dec 2010
    Posts
    59
    Rep Power
    0

    Default That really worked thanks, one more things if I may

    sorry to bother but I trying to turn this method into boolean with no luck.
    It is currently at its primary state.

    Java Code:
    private static boolean cover (int [] values, int amount, int i, List<Integer> mylist){
        if (amount == 0){
           System.out.println(mylist);
            }
        
        if (i<values.length){
            cover(values,amount,i+1,mylist);
            mylist.add(values[i]);
            cover(values,amount-values[i],i+1,mylist);
            mylist.remove(mylist.size()-1);
        }
        return true;
    }

  8. #8
    Yakg is offline Member
    Join Date
    Dec 2010
    Posts
    59
    Rep Power
    0

    Default

    the main:

    public static void main(String[] args) {

    int[] a = {5,22,13,5,7,-4};
    System.out.print(cover(a, 31));
    }
    }

  9. #9
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,004
    Blog Entries
    7
    Rep Power
    20

    Default

    Quote Originally Posted by Yakg View Post
    sorry to bother but I trying to turn this method into boolean with no luck.
    It is currently at its primary state.

    Java Code:
    private static boolean cover (int [] values, int amount, int i, List<Integer> mylist){
        if (amount == 0){
           System.out.println(mylist);
            }
        
        if (i<values.length){
            cover(values,amount,i+1,mylist);
            mylist.add(values[i]);
            cover(values,amount-values[i],i+1,mylist);
            mylist.remove(mylist.size()-1);
        }
        return true;
    }
    Your method always returns true at the end meaning to the caller of that method that it succeeded. You should only return true if the target amount == 0 or if one of the recursive invocations of that method returns true.

    kind regards,

    Jos
    cenosillicaphobia: the fear for an empty beer glass

  10. #10
    gcalvin is offline Senior Member
    Join Date
    Mar 2010
    Posts
    953
    Rep Power
    5

    Default

    Start by identifying your base cases:
    Java Code:
        public void test1() {
            int[] a = { };
            int t = 42;
            System.out.println("Should return false: " + cover(a, t));
        }
    
        public void test2() {
            int[] a = { };
            int t = 0;
            System.out.println("Should return true: " + cover(a, t));
        }
    Now start to consider some other simple test cases in terms that will recurse to one of those base cases:
    Java Code:
        public void test3() {
            int[] a = { 42 };
            int t = 42;
            System.out.println("Should return true: " + cover(a, t));
        }
    
        public void test4() {
            int[] a = { -42 };
            int t = 42;
            System.out.println("Should return true: " + cover(a, t));
        }
    
        public void test5() {
            int[] a = { 21 };
            int t = 42;
            System.out.println("Should return false: " + cover(a, t));
        }
    Now consider carefully why each of these last three tests should return true or false, in terms of the base cases already defined. In other words, you want to recurse to an empty array, and either a zero test value (returns true) or a non-zero test value (returns false). Think about how you'll reduce the size of the array and change your test value for the recursive calls.

    Since addition is commutative, you may consider the values in the array in any order without changing the result, so we may as well consider them in the order we receive them. That means for the first value n in the array and a test value t, we should consider:
    1. t (unchanged) against the remaining values in the array (after removing n)
    2. t + n against the remaining values in the array
    3. t - n against the remaining values in the array

    Hope that helps.

    -Gary-

  11. #11
    NeuroFuzzy is offline Member
    Join Date
    Sep 2010
    Posts
    10
    Rep Power
    0

    Default

    Errm, everyone's making it more complicated than it needs to be. It's easy to do this without arraylists! Well, I dunno about easy, but straightforward at least.

    To solve recursive functions, you start programming a function assuming that it works.

    Look at the code below, and work from the top of groupSumSub, like you've just wrote the class. First I figure "what are the 'base cases'/exit conditions?"
    if target=0, then you don't need to add or subtract anything and you can return true. If start is bigger than the array, you can just return false.

    We consider the first case now: if you add the number at start, can the numbers left over be combined to get target? That condition, "Can the numbers left over be combined to get the target" is the condition solved by groupSumSub, so we just call groupSumSub on the remaining numbers (start+1,nums), and subtract that number from the target. (in this way "target" represents the distance between the "current number" and the target.

    The next case is the same thing but subtracting, so we instead add the current number.

    If neither of those are true, then, if you add or subtract that number, there is no possible way you're reaching target. So we skip it, and just don't add anything to target, and move on to the next number!

    Java Code:
    	
    public boolean solution(int[] nums, int target){return groupSumSub(0,nums,target);}
    
    public boolean groupSumSub(int start, int[] nums, int target) 
    	{
    	  if(target==0)
    	    return true;
    	  if((start>=nums.length))
    	    return false;
    
    	  boolean temp=groupSumSub(start+1,nums,target-nums[start]);
    	  if(temp)
    	     return temp;
    
    	  temp=groupSumSub(start+1,nums,target+nums[start]);
    	  if(temp)
    		  return temp;
    	  
    	  return groupSumSub(start+1,nums,target);
    	}
    also note, those last 10 lines could be replaced with:
    return groupSumSub(start+1,nums,target-nums[start])||groupSumSub(start+1,nums,target-nums[start])||groupSumSub(start+1,nums,target+nums[start]);

    but for clarity's sake...

  12. #12
    gcalvin is offline Senior Member
    Join Date
    Mar 2010
    Posts
    953
    Rep Power
    5

    Default

    NeuroFuzzy has a couple of good insights here:

    1. As soon as you have a test value of 0 you can return true, no matter what's left in the array.
    2. You don't need to resize the array if you can pass a starting index.

    And since Java allows method overloading, you can do this:
    Java Code:
        public static boolean cover(int[] a, int t) {
            // to cover the syntax of your main()
            return cover(a, t, 0);
        }
    
        public static boolean cover(int[] a, int t, int i) {
            // the real recursive method
            // TODO: write the rest of this
        }
    -Gary-

  13. #13
    NeuroFuzzy is offline Member
    Join Date
    Sep 2010
    Posts
    10
    Rep Power
    0

    Default

    Yeh, So this code would be my submission for best solution:
    Java Code:
    	public static boolean groupSumSub(int start, int[] nums, int target) 
    	{
    	  if(target==0) 
    	    return true;
    	  if(start>=nums.length)
    	    return false;
    	  return 	groupSumSub(start+1,nums,target-nums[start])||
    	  			groupSumSub(start+1,nums,target+nums[start])||
    	  			groupSumSub(start+1,nums,target);
    
    	}

    Here's a test program I made cuz I'm bored, verifying that my method works.

    Java Code:
    import java.util.List;
    public class sum 
    {
    	public static String terms;
    	public static void main(String[] args)
    	{
    		int[] arr1={1,2,3,4,5};
    		int[] arr2={-1,-2,-3,-4,-5};
    		int[] arr3={5,22,13,5,7,-4};
    		int[] arr4={7,23,91,1};
    		
    		
    		System.out.println(arrstr(arr1)+" : 15 -> "+solution(arr1,15)+"  15="+terms);
    		System.out.println(arrstr(arr1)+" : 16 -> "+solution(arr1,16)+"  16="+terms);
    		System.out.println(arrstr(arr1)+" : -15 -> "+solution(arr1,-15)+"  -15="+terms);
    		System.out.println(arrstr(arr2)+" : 15 -> "+solution(arr2,15)+"  15="+terms);
    		System.out.println(arrstr(arr3)+" : 31 -> "+solution(arr3,31)+"  31="+terms);
    		System.out.println(arrstr(arr3)+" : 37 -> "+solution(arr3,37)+"  37="+terms);
    		System.out.println(arrstr(arr4)+" : 30 -> "+solution(arr4,15)+"  30="+terms);
    		System.out.println(arrstr(arr4)+" : 90 -> "+solution(arr4,15)+"  90="+terms);
    		System.out.println(arrstr(arr4)+" : 89 -> "+solution(arr4,15)+"  89="+terms);
    	}
    	
    	public static boolean solution(int[] nums, int target)
    	{
    		terms="";
    		return groupSumSub(0,nums,target);
    	}
    	public static String arrstr(int[] arr)
    	{
    		String ret="{";
    		for(int i=0;i<arr.length-1;i++)
    		{
    			ret+=arr[i]+",";
    		}
    		ret+=arr[arr.length-1]+"}";
    		return ret;
    	}
    
    	public static boolean groupSumSub(int start, int[] nums, int target) 
    	{
    	  if(target==0)
    	    return true;
    	  if((start>=nums.length))
    	    return false;
    
    	  boolean temp=groupSumSub(start+1,nums,target-nums[start]);
    	  if(temp)
    	  {
    		  
    		 terms=terms+addnum(true,nums[start]);
    	     return temp;
    	  }
    	  temp=groupSumSub(start+1,nums,target+nums[start]);
    	  if(temp)
    	  {
    		  terms=terms+addnum(false,nums[start]);
    		  return temp;
    	  }
    	  
    	  return groupSumSub(start+1,nums,target);
    	}
    	public static String addnum(boolean positive, int num)
    	{
    		if(num>=0)
    			if(positive)
    				return "+"+num;
    			else
    				return "-"+num;
    		if(num<0)
    			if(positive)
    				return ""+num;
    			else
    				return "+"+(0-num);
    		return "";
    	}
    }

  14. #14
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,004
    Blog Entries
    7
    Rep Power
    20

    Default

    Quote Originally Posted by NeuroFuzzy View Post
    Yeh, So this code would be my submission for best solution:
    Java Code:
    	public static boolean groupSumSub(int start, int[] nums, int target) 
    	{
    	  if(target==0) 
    	    return true;
    	  if(start>=nums.length)
    	    return false;
    	  return 	groupSumSub(start+1,nums,target-nums[start])||
    	  			groupSumSub(start+1,nums,target+nums[start])||
    	  			groupSumSub(start+1,nums,target);
    
    	}
    Your solution can't tell which numbers were used for the solution. My first method gives all the feasably solutions and I left it as an exercise to the OP to turn it in a boolean predicate. i.e. return as soon as a solution was found and unwind the recursion afterwards.

    kind regards,

    Jos
    cenosillicaphobia: the fear for an empty beer glass

  15. #15
    NeuroFuzzy is offline Member
    Join Date
    Sep 2010
    Posts
    10
    Rep Power
    0

    Default

    That wasn't the original problem, and if you look in the example code 1 post above my solution can be and was easily modified (If you want an arraylist replace the + String with a .add and an ArrayList)

    ;)

Similar Threads

  1. Replies: 3
    Last Post: 07-01-2010, 08:39 PM
  2. Recursion
    By mp0667 in forum New To Java
    Replies: 1
    Last Post: 01-20-2010, 07:49 AM
  3. recursion and tail-recursion differences
    By OptimusPrime in forum New To Java
    Replies: 2
    Last Post: 12-28-2009, 06:26 PM
  4. Please help with recursion
    By pheonix in forum New To Java
    Replies: 9
    Last Post: 12-27-2008, 11:41 AM
  5. Help With Recursion
    By andrew777 in forum New To Java
    Replies: 1
    Last Post: 03-29-2008, 12:51 PM

Posting Permissions

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