Given an array of ints, is it possible to choose a group of some of the ints, su

Question

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.

write a program to test your function

int d[] = {2, 5, 10, 4};

groupNoAdj(0,y, 4, 12) --> true

groupNoAdj(0, y, 4, 14) --> false

groupNoAdj(0, y, 4, 7) --> false

int f[] = {10, 2, 2, 3, 3};

groupNoAdj(0, f, 5, 15) --> ???

groupNoAdj(0, f, 5, 7) --> ???

Explanation / Answer

This is a recursion problem and it is very easy to implement. Here you go, I have implemented the code in C language. The logic remains same and can be implemented in any language. No loops used !

#include<stdio.h>
#include <stdbool.h>
bool groupNoAdj(int start, int array[],int end,int target){
   if(start>=end) return target == 0;
  
   if(groupNoAdj(start+2, array, end, target - array[start]))
   return true;
  
if(groupNoAdj(start+1, array, end, target))
   return true;
  
   return false;
}
int main(){
   int f[] = {10, 2, 2, 3, 3};
   bool value;
   value=groupNoAdj(0, f, 5, 15);
   printf(value ? "true " : "false ");
   value=groupNoAdj(0, f, 5, 7);
   printf(value ? "true " : "false ");
   int d[] = {2, 5, 10, 4};
   printf(groupNoAdj(0,d, 4, 12) ? "true " : "false ");
   printf(groupNoAdj(0, d, 4, 14) ? "true " : "false ");
   printf(groupNoAdj(0, d, 4, 7) ? "true " : "false ");
}

If you have problem at any line, do let me know in the comments. Also, the answer is true for the first one and false for the second. You can check the above example also, I have included it in my program. Compile, run and see for yourself !

Related Questions

Navigate

• Browse (All)
• Browse G
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.