#include <stdio.h>


// prototipi
int cerca_somma(int a[], int n, int s);
int stampa_somme(int a[], int n, int s, unsigned char presi[], int oldn);
void stampa_sol(int a[], int inizio, int fine, unsigned char presi[]);
int cerca_somma_dis(int a[], int n, int s);
int cerca_somma_pari(int a[], int n, int s);



int main()
{
  int s, a[9] = {4,8,15,23,42,96,-17,-3, -1};
  unsigned char x[9];

  printf(" ------- cerca_somma -------\n");
  s=67;
  printf("Ho cercato %d. Risultato: %d\n", s, cerca_somma(a, 9, s));
  s=59;
  printf("Ho cercato %d. Risultato: %d\n", s, cerca_somma(a, 9, s));
  s=22;
  printf("Ho cercato %d. Risultato: %d\n", s, cerca_somma(a, 9, s));
  s=11;
  printf("Ho cercato %d. Risultato: %d\n", s, cerca_somma(a, 9, s));
  s=-7;
  printf("Ho cercato %d. Risultato: %d\n", s, cerca_somma(a, 9, s));
  s=-9;
  printf("Ho cercato %d. Risultato: %d\n", s, cerca_somma(a, 9, s));


  printf(" ------- stampa_somme -------\n");
  s=67;
  printf("Ho cercato %d. Risultati: %d\n\n", s, stampa_somme(a, 9, s, x, 9));
  s=59;
  printf("Ho cercato %d. Risultati: %d\n\n", s, stampa_somme(a, 9, s, x, 9));
  s=22;
  printf("Ho cercato %d. Risultati: %d\n\n", s, stampa_somme(a, 9, s, x, 9));
  s=10;
  printf("Ho cercato %d. Risultati: %d\n\n", s, stampa_somme(a, 9, s, x, 9));
  s=-7;
  printf("Ho cercato %d. Risultati: %d\n\n", s, stampa_somme(a, 9, s, x, 9));
  s=-9;
  printf("Ho cercato %d. Risultati: %d\n\n", s, stampa_somme(a, 9, s, x, 9));


  printf(" ------- cerca_somma_dis -------\n");
  s=67;
  printf("Ho cercato %d. Risultato: %d\n", s, cerca_somma_dis(a, 9, s));
  s=59;
  printf("Ho cercato %d. Risultato: %d\n", s, cerca_somma_dis(a, 9, s));
  s=22;
  printf("Ho cercato %d. Risultato: %d\n", s, cerca_somma_dis(a, 9, s));
  s=11;
  printf("Ho cercato %d. Risultato: %d\n", s, cerca_somma_dis(a, 9, s));
  s=-7;
  printf("Ho cercato %d. Risultato: %d\n", s, cerca_somma_dis(a, 9, s));
  s=-9;
  printf("Ho cercato %d. Risultato: %d\n", s, cerca_somma_dis(a, 9, s));


  printf(" ------- cerca_somma_pari -------\n");
  s=67;
  printf("Ho cercato %d. Risultato: %d\n", s, cerca_somma_pari(a, 9, s));
  s=59;
  printf("Ho cercato %d. Risultato: %d\n", s, cerca_somma_pari(a, 9, s));
  s=22;
  printf("Ho cercato %d. Risultato: %d\n", s, cerca_somma_pari(a, 9, s));
  s=11;
  printf("Ho cercato %d. Risultato: %d\n", s, cerca_somma_pari(a, 9, s));
  s=-7;
  printf("Ho cercato %d. Risultato: %d\n", s, cerca_somma_pari(a, 9, s));
  s=-9;
  printf("Ho cercato %d. Risultato: %d\n", s, cerca_somma_pari(a, 9, s));


  return 0;
}


// versione vista prima del compitino che semplicemente restituisce 0/1 
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;
}


// versione che stampa tutte le soluzioni e restituisce il numero
// di soluzione (unifica le 2 versioni viste a lezione)
int stampa_somme(int a[], int n, int s, unsigned char presi[], int oldn)
{
  int tot=0;

  // caso base
  if(n==1) {
    if(a[0]==s) {
      presi[0]=1;
      stampa_sol(a,0,oldn,presi);
      return 1;
    }
    return 0;
  }

  // cerca soluzione con solo a[n-1]
  if(a[n-1]==s) {
    presi[n-1]=1;
    stampa_sol(a,n-1,oldn,presi);
    tot++;     
  }

  // cerca soluzioni con a[n-1] + altri
  presi[n-1]=1;
  tot += stampa_somme(a,n-1,s-a[n-1],presi,oldn);

  // cerca soluzioni senza a[n-1] + altri
  presi[n-1]=0;
  tot += stampa_somme(a,n-1,s,presi,oldn);

  return tot;
}

// stampa una soluzione del problema della somma
void stampa_sol(int a[], int inizio, int fine, unsigned char presi[])
{
  int i,tot=0;

  for(i=inizio;i<fine;i++)
    if(presi[i]==1) {
      tot += a[i];
      printf("%2d ",a[i]);
    }
  printf(" --> %d\n",tot);
}




// esempio di mutua ricorsivita'
// cerca somma di k>0 termini con k dispari
int cerca_somma_dis(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_pari(a,n-1,s-a[n-1]))
    return 1; 
  else if(cerca_somma_dis(a,n-1,s))
    return 1;
  return 0;
}

// cerca di ottenere n come somma di k>0 e pari 
// elementi di a[]
int cerca_somma_pari(int a[], int n, int s)
{
  if(n<=1) 
    return 0;

  if(cerca_somma_dis(a,n-1,s-a[n-1]))
    return 1; 
  else if(cerca_somma_pari(a,n-1,s))
    return 1;
  return 0;
}