Java > Recursion-2 > groupSumClump (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 this additional constraint: if there are numbers in the array that are adjacent and the identical value, they must either all be chosen, or none of them chosen. For example, with the array {1, 2, 2, 2, 5, 2}, either all three 2's in the middle must be chosen or not, all as a group. (one loop can be used to find the extent of the identical values).

groupSumClump(0, {2, 4, 8}, 10) → true
groupSumClump(0, {1, 2, 4, 8, 1}, 14) → true
groupSumClump(0, {2, 4, 4, 8}, 14) → false


Solution:

public boolean groupSumClump(int start, int[] nums, int target) {
  altArray(nums);
  if (start >= nums.length) return target == 0;
  if (groupSumClump(start+1, nums, target-nums[start])) return true;
  if (groupSumClump(start+1, nums, target)) return true;
  else return false;  
}

private void altArray(int[] nums) {
  for (int i = 0; i < nums.length; i++) {
    if (i > 0 && nums[i] == nums[i-1]) {
      nums[i-1] += nums[i];
      if (i+1 < nums.length && nums[i] != nums[i+1])
        nums[i] = 0;
      else if (i == nums.length-1)
        nums[i] = 0;
    }
  }
}


5 comments :

  1. public boolean groupSumClump(int start, int[] nums, int target) {
      if (start==nums.length) return target==0;
      for(int i=start,j=nums[i];i<nums.length-2 && j==nums[i+1];i++){
        nums[start]+=nums[i+1];
        nums[i+1]=0;
      }
      if (groupSumClump(start+1, nums, target-nums[start])) return true;
      if (groupSumClump(start+1, nums, target)) return true;
      return false;
    }

    ReplyDelete
  2. public boolean groupSumClump(int start, int[] nums, int target) {
    if (start >= nums.length) return (target == 0);
    if (start<nums.length-1 && nums[start]==nums[start+1])
    {
    return groupSumClump(start+2, nums, target);
    }
    if (groupSumClump(start + 1, nums, target)) return true;
    if (groupSumClump(start + 1, nums, target - nums[start])) return true;
    return false;
    }

    ReplyDelete
  3. About the solution above from October 16. Am I missing something or does it not cover the case where all the identical numbers are used? I tested it and it works however from the visible solutions there is no case where all the identical numbers are used.

    ReplyDelete
  4. public boolean groupSumClump(int start, int[] nums, int target) {
    if(start>=nums.length)return target==0;
    int i = nums[start];int x = 0;
    while((x+start)<nums.length&&nums[start+x]==i)
    x++;

    if (groupSumClump(start+x, nums, target-x*i)) return true;
    if (groupSumClump(start+x, nums, target)) return true;


    return false;
    }

    ReplyDelete
  5. About the solution above from October 16.
    I solved the same way, but to satisfy all the requirements I added one more check, and yet it works, but it depends on what order you put.
    public boolean groupSumClump(int start, int[] nums, int target) {
    if ( start >= nums.length ) return target == 0 ;

    if ( start < nums.length -1 && nums[start] == nums[start+1]){
    return groupSumClump( start + 2 , nums , target ) ;
    }
    if ( start < nums.length -1 && nums[start] == nums[start+1]){
    return groupSumClump( start + 2 , nums , target - nums[start]-nums[start] ) ;
    }

    if ( groupSumClump( start + 1 , nums , target - nums[start]) ) return true;
    if ( groupSumClump ( 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