For further help with Coding Bat (Java), please check out my books. I am also available for tutoring.
Finally we’ve reached the last section of Coding Bat: Recursion-2. Those nine exercises are all very similar. Once you’ve figured out one you can probably solve the others immediately.
I’ll just walk you through the general strategy, using the first exercise as an example: The method “groupSum” takes three arguments. The first, “start”, is the index of an array of integers, the second is the array of integers in question, and the third, “target” is the target value. Now, “start” increases by one with each recursive call. If this value is greater than or equal to the length of the array, then the entire array has been processed. At this point, only the evaluation step has to be done, which consists of checking whether the target value is zero.
“Why zero?”, you may ask. If “target” equals zero, then it is possible to pick a group of integers from the array that sum up to the target value. The calculation is done by selecting each value of the array and in one case subtracting it from “target”, while in the other leaving “target” unchanged. Thus, all possible combinations will eventually be checked. Finally, the method returns “true” once one of the results is “true”, which is a property of short-circuit evaluation of logical disjunctions.
All solutions were successfully tested on 28 March 2013.
groupSum:
public boolean groupSum(int start, int[] nums, int target) {
if (start >= nums.length) return target == 0;
return groupSum(start + 1, nums, target - nums[start])
|| groupSum(start + 1, nums, target);
}
groupSum6:
public boolean groupSum6(int start, int[] nums, int target) {
if (start >= nums.length) return target == 0;
if (nums[start] == 6)
return groupSum6(start + 1, nums, target - nums[start]);
return groupSum6(start + 1, nums, target - nums[start])
|| groupSum6(start + 1, nums, target);
}
groupNoAdj:
public boolean groupNoAdj(int start, int[] nums, int target) {
if (start >= nums.length) return target == 0;
return groupNoAdj(start + 2, nums, target - nums[start])
|| groupNoAdj(start + 1, nums, target);
}
groupSum5:
public boolean groupSum5(int start, int[] nums, int target) {
if (start >= nums.length) return target == 0;
if (nums[start] % 5 == 0) {
if (start < nums.length - 1 && nums[start + 1] == 1)
return groupSum5(start + 2, nums, target - nums[start]);
return groupSum5(start + 1, nums, target - nums[start]);
}
return groupSum5(start + 1, nums, target - nums[start])
|| groupSum5(start + 1, nums, target);
}
[/sourcecode]
<b>groupSumClump:</b>
[sourcecode language="Java" gutter="true"]
public boolean groupSumClump(int start, int[] nums, int target) {
if (start >= nums.length) return target == 0;
int sum = nums[start];
int count = 1;
for (int i = start + 1; i < nums.length; i++)
if (nums[i] == nums[start]) {
sum += nums[i];
count++;
}
return groupSumClump(start + count, nums, target - sum)
|| groupSumClump(start + count, nums, target);
}
[/sourcecode]
<b>splitArray:</b>
[sourcecode language="Java" gutter="true"]
public boolean splitArray(int[] nums) {
return helper(0, nums, 0, 0);
}
private boolean helper(int start, int[] nums, int sum1, int sum2) {
if (start >= nums.length) return sum1 == sum2;
return helper(start + 1, nums, sum1 + nums[start], sum2)
|| helper(start + 1, nums, sum1, sum2 + nums[start]);
}
splitOdd10:
public boolean splitOdd10(int[] nums) {
return helper(0, nums, 0, 0);
}
private boolean helper(int start, int[] nums, int sum1, int sum2) {
if (start >= nums.length)
return sum1 % 10 == 0 && sum2 % 2 == 1 || sum1 % 2 == 1
&& sum2 % 10 == 0;
return helper(start + 1, nums, sum1 + nums[start], sum2)
|| helper(start + 1, nums, sum1, sum2 + nums[start]);
}
split53:
public boolean split53(int[] nums) {
return helper(0, nums, 0, 0);
}
private boolean helper(int start, int[] nums, int sum1, int sum2) {
if (start >= nums.length) return sum1 == sum2;
if (nums[start] % 5 == 0)
return helper(start + 1, nums, sum1 + nums[start], sum2);
if (nums[start] % 3 == 0)
return helper(start + 1, nums, sum1, sum2 + nums[start]);
return helper(start + 1, nums, sum1 + nums[start], sum2)
|| helper(start + 1, nums, sum1, sum2 + nums[start]);
}
For further help with Coding Bat (Java), please check out my books. I am also available for tutoring.
“return helper(start + 1, nums, sum1 + nums[start], sum2)
|| helper(start + 1, nums, sum1, sum2 + nums[start]);”
How does the or work in a return statement? Does this cause the recursion to alternate?
I can’t find anything about returning an or statement anywhere.
Thanks,
Luke
Since the return statement uses an boolean operator, the function has to return a boolean value. This means that once the base case is reached in all recursive calls, at the latest, the final value can be computed. Here is an illustration, using a greatly simplified example:
foo n | n == 0 = False | otherwise = True && foo (n-1)Now simply trace the execution, using a small value for n, maybe n == 3:
I’ve used the and-operator in this example because it is more realistic. Boolean expressions are normally evaluated lazily, which means that superfluous computations are avoided. In the case of an or-expression, this means that the result would be True as soon as the first variable evaluates to True. Likewise, the first False in an and-expression would evaluate the entire expression to False, which is why I chose to use False for the base case in the preceding example, so that it would be the last value to be added.
I had a similar question so I ended up writing it out to understand.
Heres a simple example to clarify what happens.
nums = {2, 3, 5} // should return true {2, 3} and {5}
two initial calls are made passing the values:
A B
helper(1, nums, 2, 0) || helper(1, nums, 0, 2)
what follows is more calls branching out from those values:
A: helper(2, nums, 5, 0) || helper(2, nums, 2, 3)
B: helper(2, nums, 3, 2) || helper(2, nums, 0, 5)
Each one making more calls that branch out until a final boolean value is returned:
if (start >= nums.length) return sum1 == sum2;
Heres the whole picture: (nums is passed ill just show (start, sum1, sum2) )
helper(0, nums, 0, 0);
/ \
(1, 2, 0) || (1, 0, 2)
/ \ / \
(2, 5, 0) || (2, 2, 3) (2, 3, 2) || (2, 0, 5)
/ \ / \ / \ / \
(3, 10, 0) (3, 5, 5) (3, 7, 3) (3, 2, 8) (3, 8, 2) (3, 3, 7) (3, 5, 5) (3, 0, 10)
F T F F F F T F
Following the calls ends up returning T since each one is an OR.
The three bitwise operators AND (&&), OR (||), and NOT (^) deal with what cases will return true. If you use AND, both or all cases must be true in order for the return statement to return true (exa: return (x % 2 == 0 && x > 0) will return true only if the value x is even and greater than zero). If you use OR, only one of the cases needs to be true for the return statement to return true, but it will return true no matter how many of the cases are true (exa: return (x % 2 == 0 || x > 0) will return true if x is even [whether it’s positive or negative] or if x is greater than zero [whether it’s even or odd]). If you use NOT, only one of the cases is allowed to be true for the return statement to return true (exa: return (x % 2 == 0 ^ x > 0) will return true only if x is even and negative or odd and positive, because it can not be both even and positive).
You are mixing up bitwise and logical operators.
I believe there is a pitfall in your groupSumClump solution: if there is non-clumped repetition, it will include all of the repeated values, even though they are outside of the clump.
For example, consider: groupSumClump(0, {6, 1, 1, 9, 1}, 8) → true
This example will fail, because all three ones will be counted, even though the last is not part of the clump. More over, the 9 would be skipped because count equals 3, and the final one would be considered again. Consequently, I believe your solution would also fail on:
groupSumClump(0, {6, 1, 1, 11, 1}, 10) → false
groupSumClump(0, {3, 1, 1, 9, 1}, 10) → true
A small change fixes the solution by exiting the loop when . My solution follows:
Thanks for posting your solutions!
Yes, you’re right. Maybe you should submit those test cases to Nick Parlante?
Hi
In the splitOdd10 method, isn’t the second part (the ) redundant , I mean the method works even like this ,without the sum2 +value part
public static boolean splitOdd10(int[] nums) {
int index = 0;
int sum1 = 0;
int sum2 = 0;
return recArray(nums, index, sum1, sum2);
}
private static boolean recArray ( int[] nums, int index, int sum1, int sum2 ) {
if ( index >= nums.length ) {
return (sum2%10 == 0 && sum1%2 !=0) ;
}
int value = nums[index];
return (recArray(nums, index + 1, sum1 + value, sum2));
}
Can you post or send me an answer in groupSum using iteration or another way without using recursion?
At last I have come up with an answer but it’s not efficient since I didn’t put conditions to fasten up the process. Here’s mine.
for(int i=start; i<nums.length; i++){
for(int j=i; j<nums.length; j++){
int sum=nums[i];
for(int k=j+1; k<nums.length; k++)
sum+=nums[k];
if(sum==target)
return true;
}
}
return target==0;
umm…Alois…it works on codebat, but not in real life
i tried it on the array {12, 3, 56, 7, 18, 9, 50, 12} with target 28
it returned false.
I admire the effort though, it took me hours to write the following:
public boolean groupSum(int start, int[] nums, int target){
if(start>0){int nums1[] = new int[nums.length-start];
for(int a=0;a<nums1.length;a++){nums1[a] = nums[a+start];}
return groupSum(0,nums1,target);} //use recursion once, but u can rewrite it out
if(nums.length==0) return target == 0;
boolean[] bool = new boolean[nums.length+1];
for(int a=0;a<bool.length;a++)bool[a] = false;
while(!bool[bool.length-1]){
int aa = 0;
for(int a=0;a<nums.length;a++){
if(bool[a]) aa+=nums[a];
}
if(aa==target) return true;
int a = 0; while(bool[a]){bool[a] = false;a++;} bool[a] = true;
}
return false;
}
It’s quite amazing what kind of requests are sometimes issued by random strangers on the Internet.
how is the group sum working without returning true or false?
splitOdd10 can be further reduced with only one exit condition instead of OR…
public boolean splitOdd10(int[] nums) {
return helper(0, nums, 0, 0);
}
public boolean helper(int start, int[] a, int leftsum, int rightsum) {
if(start >= a.length) return (leftsum % 10 == 0) && (rightsum % 2 == 1);
return helper(start + 1, a, leftsum + a[start], rightsum) ||
helper(start + 1, a, leftsum, rightsum + a[start]);
}
Notice the exit condition , no need to check whether rightsum % 10 == && leftsum % 2 == 1
Ankit, I think it is not very good idea. Because your soltion may increase count of recursive calls
As example:
1) array {1,10}
Gregor’s solution gets: 3 calls of “helper”.
Your solution : 6 calls.
2) array {10, 7, 5, 5, 2}
6 calls vs 22 calls
Hi,
I have a question on second problem, groupSum6:
I see you have added a if condition to check whether the array value is 6 or not. But the condition inside the if and the next statement both are decrementing the target by 1. So why the check of 6.
I understand the problem is for 6 to be added, but i am nto able to understand is how the if condition is helping.
if (nums[start] == 6)
return groupSum6(start + 1, nums, target – nums[start]);
return groupSum6(start + 1, nums, target – nums[start])
Regards
Lucky…
Can someone explain to me how the groupSum5 solution will only succeed if a multiple of 5 is included in the solution? If there isn’t a multiple of 5 in the array, won’t it run exactly like the first groupSum problem?
What is the answer to splitArray
I can’t seem to find it anywhere.