Results 1 to 3 of 3
  1. #1
    neilh is offline Member
    Join Date
    Apr 2008
    Posts
    2
    Rep Power
    0

    Default Recurssion Help!

    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.

  2. #2
    neilh is offline Member
    Join Date
    Apr 2008
    Posts
    2
    Rep Power
    0

    Default

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

  3. #3
    Zosden's Avatar
    Zosden is offline Senior Member
    Join Date
    Apr 2008
    Posts
    384
    Rep Power
    7

    Default

    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
    My IP address is 127.0.0.1

Posting Permissions

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