Results 1 to 15 of 15
 02092011, 10:42 AM #1Member
 Join Date
 Dec 2010
 Posts
 59
 Rep Power
 0
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+134=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 = j1; if (i>1 && values[i] < key){ values[i+1] = values[i]; cover (values,i=i1,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.length1){ 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,neg1,helper,i); //if <
Your help is much appreciated thanks.
 02092011, 10:58 AM #2
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 13,010
 Blog Entries
 7
 Rep Power
 20
 02092011, 11:06 AM #3Member
 Join Date
 Dec 2010
 Posts
 59
 Rep Power
 0
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.
 02092011, 11:25 AM #4
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 13,010
 Blog Entries
 7
 Rep Power
 20
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, suma[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>()); } }
Joscenosillicaphobia: the fear for an empty beer glass
 02092011, 11:38 AM #5Member
 Join Date
 Dec 2010
 Posts
 59
 Rep Power
 0
Great but, I can't use the list
could I use an array instead?
I will check if it works.
 02092011, 12:15 PM #6
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 13,010
 Blog Entries
 7
 Rep Power
 20
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,
Joscenosillicaphobia: the fear for an empty beer glass
 02102011, 01:36 PM #7Member
 Join Date
 Dec 2010
 Posts
 59
 Rep Power
 0
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,amountvalues[i],i+1,mylist); mylist.remove(mylist.size()1); } return true; }
 02102011, 01:37 PM #8Member
 Join Date
 Dec 2010
 Posts
 59
 Rep Power
 0
the main:
public static void main(String[] args) {
int[] a = {5,22,13,5,7,4};
System.out.print(cover(a, 31));
}
}
 02102011, 01:48 PM #9
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 13,010
 Blog Entries
 7
 Rep Power
 20
cenosillicaphobia: the fear for an empty beer glass
 02102011, 02:42 PM #10Senior Member
 Join Date
 Mar 2010
 Posts
 953
 Rep Power
 5
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)); }
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)); }
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
 02102011, 02:43 PM #11Member
 Join Date
 Sep 2010
 Posts
 10
 Rep Power
 0
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,targetnums[start]); if(temp) return temp; temp=groupSumSub(start+1,nums,target+nums[start]); if(temp) return temp; return groupSumSub(start+1,nums,target); }
return groupSumSub(start+1,nums,targetnums[start])groupSumSub(start+1,nums,targetnums[start])groupSumSub(start+1,nums,target+nums[start]);
but for clarity's sake...
 02102011, 02:57 PM #12Senior Member
 Join Date
 Mar 2010
 Posts
 953
 Rep Power
 5
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 }
 02102011, 03:10 PM #13Member
 Join Date
 Sep 2010
 Posts
 10
 Rep Power
 0
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,targetnums[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.length1;i++) { ret+=arr[i]+","; } ret+=arr[arr.length1]+"}"; 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,targetnums[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 "+"+(0num); return ""; } }
 02102011, 03:25 PM #14
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 13,010
 Blog Entries
 7
 Rep Power
 20
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,
Joscenosillicaphobia: the fear for an empty beer glass
 02102011, 09:15 PM #15Member
 Join Date
 Sep 2010
 Posts
 10
 Rep Power
 0
Similar Threads

A clever way of doing this ... (avoiding a LOT of ifelse statements)
By doejohn in forum New To JavaReplies: 3Last Post: 07012010, 08:39 PM 
Recursion
By mp0667 in forum New To JavaReplies: 1Last Post: 01202010, 07:49 AM 
recursion and tailrecursion differences
By OptimusPrime in forum New To JavaReplies: 2Last Post: 12282009, 06:26 PM 
Please help with recursion
By pheonix in forum New To JavaReplies: 9Last Post: 12272008, 11:41 AM 
Help With Recursion
By andrew777 in forum New To JavaReplies: 1Last Post: 03292008, 12:51 PM
Bookmarks