Recurssion Help!

[neilh]

So I did a problem with this instruction

"Given an array of ints, is it possible to choose a group of some of the ints, beginning at the start index, such that the group sums to the given target? However, with the additional constraint that all 6's must be chosen. (No loops needed.)

groupSum6(0, {5, 6, 2}, 8) → true
groupSum6(0, {5, 6, 2}, 9) → false
groupSum6(0, {5, 6, 2}, 7) → false
"
And the code is here

public boolean groupSum6(int start, int[] nums, int target) {
if(start>=nums.length)
return(target==0);
if(groupSum6(start+1, nums, target-nums[start]))
return true;
if(nums[start]==6)
return groupSum6(start+1, nums, target-6);
if(groupSum6(start+1, nums, target))
return true;

return false;
}


I don't understand many things about this

First I repeated the two similar recursion steps (bolded them), but I dont understand why I had to do this? Second I don't understand why I had to put if(nums[start]==6) before if(groupSum6(start+1,nums,target))? Can anyone explain this to me? Thanks.

[neilh]

Also if I have an array {6,6} and want a target 18, why doesn't it return true?

[Zosden]

I don't think recursion is the best technique for this type of problem. The only way I see recursion helping is to search through the list for the sixes. I would just use brute force with loops instead to figure this out. You could use recursion, but I would still use some sort of searching technique to figure out how many sixes I have, and then try to find other numbers that works with this. many sixes if possible. Actually on second thought what you could do is pull out all the sixes then create a new array that you sort. then just simply brute force. It would cut down on the number checks you would have to do thus making your algorithm faster. This technique would only really help for larger n. I would recommended checking out Array.sort I believe is the class in the java api