Question

// Given an int array of size elements, determine if there are k elements that add up to sum.
// The array holds integers, both positive and negative and zero.
// It is not possible to add zero elements (that's when k==0) to any sum, not even zero.
// It is not possible to add any elements from an empty array.
// Must be recursive and not iterative
//bool K_element_sum(size_t k, int sum, int arr[], size_t size){}

Answer 1

In this program, we have to check if the given array contains k elements that sum up to the given sum

we will use a recursive implementation to do this.

The following are the base conditions:

1.) if k is 0 and sum is 0, return true

2.) if k is 0 and sum is not zero, return false

3.) if size if 0, return false

The recursive definition is as follows:

1.) if K_element_sum(k-1, sum-arr[size-1], arr, size-1) is true, then return true

2.) if K_element_sum(k,sum,arr,size-1) is true, then return true

3.) otherwise return false

function:

bool K_element_sum(size_t k, int sum, int arr[], size_t size){
if(k==0 && sum == 0)
   return true;
if(k==0)
   return false;
if(size==0)
   return false;
if(K_element_sum(k-1, sum-arr[size-1], arr, size-1))
   return true;
if(K_element_sum(k,sum,arr,size-1))
   return true;
return false;
}

sample program to test this function:

#include <iostream>

using namespace std;

bool K_element_sum(size_t k, int sum, int arr[], size_t size){
if(k==0 && sum == 0)
   return true;
if(k==0)
   return false;
if(size==0)
   return false;
if(K_element_sum(k-1, sum-arr[size-1], arr, size-1))
   return true;
if(K_element_sum(k,sum,arr,size-1))
   return true;
return false;
}

int main(){
int arr[] = {1,2,3,4,5};
int k = 2;
int sum = 6;
int size = sizeof(arr) / sizeof(arr[0]);
if (K_element_sum(k, sum, arr, size))
cout<<"True\n";
else
cout<<"False\n";
return 0;
}

output: