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;
}
can you explain why that is
ReplyDelete//If you want to start from first element:
ReplyDeleteif(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;
public boolean groupNoAdj(int start, int[] nums, int target) {
ReplyDelete/* 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)
*/
public boolean groupNoAdj(int start, int[] nums, int target) {
ReplyDeleteif (start >= nums.length)
{
return target == 0;
}
else
{
return groupNoAdj(start + 2, nums, target - nums[start]) ||
groupNoAdj(start + 1, nums, target);
}
}
private final boolean groupNoAdj(int start, int[] nums, int target) {
ReplyDeleteif(start >= nums.length){
return (target == 0);
}
return groupNoAdj(start + 2, nums, target - nums[start]) || groupNoAdj(start + 1, nums, target);
}