I am a bit confused as to why my solution below, is not giving the proper answer. I did some digging and I'm guessing it has to do with the way the calls work? I thought that both ways were the same but that is not the case, but I do not completely understand what mine is returning incorrectly. This is the research I did before hand: https://softwareengineering.stackexchange.com/questions/333247/why-does-recursion-return-the-first-call-in-the-stack-and-not-the-last
Problem:
Given an array of ints, is it possible to divide the ints into two groups, so that the sum of the two groups is the same, with these constraints: all the values that are multiple of 5 must be in one group, and all the values that are a multiple of 3 (and not a multiple of 5) must be in the other. (No loops needed.)
Example:
split53([1, 1]) → true
split53([1, 1, 1]) → false
split53([2, 4, 2]) → true
My Answer:
public boolean split53Helper(int start, int [] nums, int group3, int group5){
if(start >= nums.length){
return group3 == group5;
}
if(nums[start] % 3 == 0 ){
if (split53Helper(start + 1, nums, group3 + nums[start], group5)){
return true;
}
}
if(nums[start] % 5 == 0){
if (split53Helper(start + 1, nums, group3, group5 + nums[start])){
return true;
}
}
if(split53Helper(start+1, nums, group3 + nums[start], group5))
return true;
if(split53Helper(start+1, nums, group3, group5 + nums[start]))
return true;
return false;
}
Correct Solution:
public boolean split53(int[] nums) {
return split53Helper(0, nums, 0, 0);
}
public boolean split53Helper(int start, int[] nums, int mult5, int mult3) {
if(start >= nums.length)
return mult5 == mult3;
if(nums[start] % 5 == 0)
return split53Helper(start+1, nums, mult5 + nums[start], mult3);
if(nums[start] % 3 == 0)
return split53Helper(start+1, nums, mult5, mult3 + nums[start]);
if(split53Helper(start+1, nums, mult5 + nums[start], mult3))
return true;
if(split53Helper(start+1, nums, mult5, mult3 + nums[start]))
return true;
return false;
}
Is my code not returning the last call? If so, when would I use one method of returning over the other? If there is already a thorough explanation just let me know. I thought I understood how the stacks and function calls worked but now I'm worried I'm moving in the wrong direction.
Here's the correct solution, rewritten to look more similar to your answer:
public boolean split53Helper(int start, int [] nums, int group3, int group5){
if(start >= nums.length){
return group3 == group5;
}
if(nums[start] % 3 == 0 ){
if (split53Helper(start + 1, nums, group3 + nums[start], group5)){
return true;
} else {
return false; // <-------
}
}
if(nums[start] % 5 == 0){
if (split53Helper(start + 1, nums, group3, group5 + nums[start])){
return true;
} else {
return false; // <-------
}
}
if(split53Helper(start+1, nums, group3 + nums[start], group5))
return true;
if(split53Helper(start+1, nums, group3, group5 + nums[start]))
return true;
return false;
}
Now you should see how your answer is different from the correct solution. If the first recursive call returns false, your answer would continue on to call the third and fourth recursive call, whereas the correct solution will not.
When a recursive method deals with arrays, it almost always follows this "do something to one element, and then (recursively) do it to the rest of the elements" pattern. The recursive calls are asking "can the rest of the array be divided into 2 groups that sums to the same number...?".
When an element is divisible by 3, you put it in the 3's group and ask that same question, hence calling:
split53Helper(start + 1, nums, group3 + nums[start], group5)
If the answer to this question is "no", you shouldn't then ask "well what if I put it in the 5's group?" (I'm referring to the 4th recursive call in your answer)
split53Helper(start + 1, nums, group3, group5 + nums[start])
You can't put it in the 5's group because the element is known to be divisible by 3.
This is why you should return immediately when you know it's divisible by 3, and the rest can't be divided into groups.
Эта статья взята из Интернета, укажите источник при перепечатке.
Если есть какие-либо нарушения, пожалуйста, свяжитесь с[email protected] Удалить.
я говорю два предложения