#include <stdio.h>
#include <stdlib.h>
#include <time.h>

void decomp(int *tab, int taille, int m)
{ for(int i=0; i<taille; i++) tab[i]=m&1, m>>=1; }

int subsetsum(int *ensemble, int taille, int m)
{ int base2[taille], i, j, somme, max=1<<taille;
  for(i=0; i<max; i++)
  { somme=0;
    decomp(base2, taille, i);
    for(j=0; j<taille; j++) if(base2[j]) somme+=ensemble[j];
    if(somme==m) return i;
  }
  return -1;
}

int subsetsum_recursif(int *ensemble, int taille, int profondeur, int m, int somme)
{ if(somme==m) return 1;
  if(taille==profondeur) return -1;
  if(somme>m) return -1;
  if(subsetsum_recursif(ensemble, taille, profondeur+1, m, somme+ensemble[profondeur])==1)
   return printf("%d ", ensemble[profondeur]), 1;
  return subsetsum_recursif(ensemble, taille, profondeur+1, m, somme);
}
int subsetsum_recursif2(int *ensemble, int taille, int profondeur, int m, int somme)
{ if(somme==m) return 0;
  if(taille==profondeur) return -1;
  if(somme>m) return -1;
  int r=subsetsum_recursif2(ensemble, taille, profondeur+1, m, somme+ensemble[profondeur]);
  if(r>=0) return r+(1<<profondeur);
  return subsetsum_recursif2(ensemble, taille, profondeur+1, m, somme);
}
int subr(int*t,int n,int s) { return subsetsum_recursif2(t,n,0,s,0); }

int subr2(int*t,int n,int s)
{ if(s==0) return 0;
  if(n==0) return -1;
  if(t[n-1]<=s)
  { int r=subr2(t,n-1,s-t[n-1]);
    if(r>=0) return r+(1<<(n-1));
  }
  return subr2(t,n-1,s);
}
int somme(int*t, int m)
{ int s=0;
  for(;m;m>>=1,t++) if(m&1) s+=*t;
  return s;
}
typedef int subs(int*,int ,int);
void test(int n,subs sub,const char*nom,unsigned z)
{ int t[n], i, nn=(1<<n)/n, s=0;
  for(i=0;i<n;i++) t[i]=z=(z*1234567+1)%nn;
  for(i=0;i<n;i++) if(z*(i+1)&(1<<i)) s+=t[i];  
  int a=clock();
  int m=sub(t,n,s);
  a=clock()-a;
  printf("%-10s %2d %8x %6d %s\n",nom,n,m,a,s==somme(t,m)?" bon":"faux");
}

void american_flag(int *t,int n)
{ typedef unsigned char (*t4)[4];
  int i,j,l,c[256],d[256],u[n],*v=u,*w;
  for(l=0;l<4;l++)  // choix du chiffre de poids 256^l
  { for(j=0;j<256;j++) c[j]=0;   // mise à zéro des 256 compteurs
    for(i=0;i<n;i++) c[((t4)t)[i][l]]++; // comptage (calcul des hauteurs des 256 piles)
    d[0]=0;
    for(j=0;j<255;j++) d[j+1]=d[j]+c[j]; // sommes partielles des compteurs (empilement des 256 pil
    if(l==3) for(j=128;j--;) d[j]+=n-d[128], d[j+128]-=d[128]; // gestion du signe (échange des 128
    for(i=0;i<n;i++) v[d[((t4)t)[i][l]]++]=t[i]; // répartition dans les différentes piles
    w=t,t=v,v=w;    // échange de t et u
  }
}
void listesomme(int*t,int n,int s,int *ts)
{ while(n) --n,listesomme(t,n,s+t[n],ts+(1<<n));
  *ts=s;
}
void listesommetri(int*t,int n,int*ts)
{ listesomme(t,n,0,ts), american_flag(ts,1<<n); }

int subr3(int*t,int n, int s)
{ if(s==0) return 0;
  if(n==1 && *t==s) return 1;
  if(n<2) return -1;
  int m=n/2, p=n-m, mm=1<<m, pp=1<<p, ts[mm], st[pp], i=0, j=pp-1;
  listesommetri(t  ,m,ts);
  listesommetri(t+m,p,st);
  while(i<mm && j>=0 && ts[i]+st[j]!=s) if(ts[i]+st[j]<s) i++; else j--;
  if(i==mm || j<0) return -1;
  return subr3(t,m,ts[i])+(subr3(t+m,p,st[j])<<m);
}
void tri_insertion(int*t,int n)
{ for(int i=0,j,x;++i<n;t[j]=x)
   for(x=t[j=i];j && t[j-1]>x;j--) t[j]=t[j-1];
}
int ttt(int*t,int*u,int m)  // somme(t,m)=somme(u,ttt(t,u,m))  si t[] est une permutation de u[].
{ int p=0, i, j;            // On permute les bits de m, comme on permute t[] pour obtenir u[].
  for(i=0;m;i++) if(m>>i&1) {
    for(j=0;(p>>j&1) || t[i]!=u[j];j++) ;
    p+=1<<j, m-=1<<i;
  }
  return p;
}
void retourne(int*t,int*u) {for(;t<--u;) {int x=*t; *t++=*u,*u=x;}}
int subrtri(int*t,int n,int s)
{ int tt[n], i;
  for(i=0;i<n;i++) tt[i]=t[i];
  tri_insertion(tt,n);
  retourne(tt,tt+n);
  int r=subr(tt,n,s);
  return r<0?r:ttt(tt,t,r);
}
int subr2tri(int*t,int n,int s)
{ int tt[n], i;
  for(i=0;i<n;i++) tt[i]=t[i];
  tri_insertion(tt,n);
  int r=subr2(tt,n,s);
  return r<0?r:ttt(tt,t,r);
}

#define nom(truc) truc,#truc
int main(){
    int ensemble[] = {5, 10, 12, 13, 15, 18};
    int taille=6;
    printf("%d\n", subsetsum_recursif(ensemble, taille, 0, 30, 0));
    for(int n=20;n<30;n++)
    { if(n<=24) test(n,nom(subsetsum),1);
      test(n,nom(subr),1);
      test(n,nom(subrtri),1);
      test(n,nom(subr2),1);
      test(n,nom(subr2tri),1);
      test(n,nom(subr3),1);
    }
    return 0;
}