#include <stdio.h>

int cerca_somma(int [ ], int n, int s);

int main() {

  int a[5] = {3, 2, 5, 1, -4};

  printf("Qui deve stampare 1: %d\n",cerca_somma(a,5,4));
  printf("Qui deve stampare 0: %d\n",cerca_somma(a,5,-5));
  printf("Qui deve stampare 0: %d\n",cerca_somma(a,5,12));
  printf("Qui deve stampare 1: %d\n",cerca_somma(a,5,-1));
  printf("Qui deve stampare 1: %d\n",cerca_somma(a,5,-3));
  return 0;
}

// cerca se esiste un sottoinsieme di a[] la cui somma e' s
int cerca_somma(int a[], int n, int s)
{
  if(n==1) {
    if(a[0]==s)
      return 1;
    else 
      return 0;
  }
  if(a[n-1]==s)
    return 1;     // trovato con k=1
  else if(cerca_somma(a,n-1,s-a[n-1]))
    return 1; 
  else if(cerca_somma(a,n-1,s))
    return 1;
  return 0;
}