Java > Recursion-2 > groupSum5 (CodingBat Solution)

Problem:

Given an array of ints, is it possible to choose a group of some of the ints, such that the group sums to the given target with these additional constraints: all multiples of 5 in the array must be included in the group. If the value immediately following a multiple of 5 is 1, it must not be chosen. (No loops needed.)

groupSum5(0, {2, 5, 10, 4}, 19) → true
groupSum5(0, {2, 5, 10, 4}, 17) → true
groupSum5(0, {2, 5, 10, 4}, 12) → false


Solution:

public boolean groupSum5(int start, int[] nums, int target) {
  if (start >= nums.length) return (target == 0);
  if (groupSum5(start+1, nums, target-nums[start]) && checkOne(start, nums))
    return true;
  if (nums[start] % 5 != 0 && groupSum5(start+1, nums, target)) return true;
  return false;
}

private boolean checkOne(int start, int[] nums) {
  if (start == 0) return true;
  if (start > 0 && nums[start-1] % 5 == 0 && nums[start] == 1)
    return false;
  else
    return true;
}


3 comments :

  1. public boolean groupSum5(int start, int[] nums, int target) {
    if(start==nums.length) return target==0;
    if(nums[start]%5==0 && start < nums.length-1 && nums[start+1]==1) nums[start+1]=0;
    if(groupSum5(start+1,nums,target-nums[start])) return true;
    if(nums[start]%5!=0 && groupSum5(start+1,nums,target)) return true;
    return false;
    }

    ReplyDelete
  2. 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){
    //must choose start & not start + 1
    if( groupSum5(start+2, nums, target-nums[start]) ){
    return true;
    }
    } else {
    //must choose start
    if( groupSum5(start+1, nums, target-nums[start]) ){
    return true;
    }
    }
    } else {
    //explore choosing start and not choosing start
    if( groupSum5(start+1, nums, target-nums[start]) ){
    return true;
    }
    if( groupSum5(start+1, nums, target) ){
    return true;
    }
    }
    return false;
    }

    ReplyDelete
  3. public boolean groupSum5(int start, int[] nums, int target) {
    if (start > nums.length - 1) return (target == 0);
    if (start > 0) {
    if ((nums[start] != 1 || nums[start-1] % 5 != 0) && groupSum5(start + 1, nums, target - nums[start])) return true;
    }
    else if (groupSum5(start + 1, nums, target - nums[start])) return true;
    if (nums[start] % 5 != 0 && groupSum5(start + 1, nums, target)) return true;
    return false;
    }

    ReplyDelete

Follow Me

If you like our content, feel free to follow me to stay updated.

Subscribe

Enter your email address:

We hate spam as much as you do.

Upload Material

Got an exam, project, tutorial video, exercise, solutions, unsolved problem, question, solution manual? We are open to any coding material. Why not upload?

Upload

Copyright © 2012 - 2014 Java Problems  --  About  --  Attribution  --  Privacy Policy  --  Terms of Use  --  Contact