Java > Recursion-2 > groupNoAdj (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 a value in the array is chosen to be in the group, the value immediately following it in the array must not be chosen. (No loops needed.)

groupNoAdj(0, {2, 5, 10, 4}, 12) → true
groupNoAdj(0, {2, 5, 10, 4}, 14) → false
groupNoAdj(0, {2, 5, 10, 4}, 7) → false


Solution:

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

}


3 comments :

  1. can you explain why that is

    ReplyDelete
  2. //If you want to start from first element:

    if(start >= nums.length){
    return target==0;
    }

    if (groupNoAdj(start+2,nums,target-nums[start]))return true;


    if(groupNoAdj(start+1,nums,target)) return true;

    return false;

    ReplyDelete
  3. public boolean groupNoAdj(int start, int[] nums, int target) {

    /* you end the recursion of loops when you reach the end of the NUMS array, and you get true or false if you find enough numbers needed for the TARGET number
    */

    if(start >= nums.length){
    return target == 0;
    }

    /* when you select an element of the array you step forward 2 and call the recursion again, if somewher you reach the goal in called recursions you will get TRUE returned somepoint (or not)
    */

    if( groupNoAdj(start + 2, nums, target - nums[start])) return true;

    /* here you dont select the actual element of NUMS so you step 1 forward, and dont change the target
    */

    if( groupNoAdj(start + 1, nums, target)) return true;

    /* if you never got to reach a the goal u just return a false
    */

    return false;

    }
    /* this kind of recursion is a Trial of all the possible selection of the NUMS elements, imagine like a tree, where each leaf is another call of the method with the next neeeded to try out parameters, and if you find a TRUE returned you go back to the root(wich is the firs call of method)
    */

    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