sumofsub.rar_SumOfSub_回溯法_回溯法子集和_子集和数_子集和数问题

#define MAXNUM 100 #include <stdio.h> #include <string.h> #include <vector> using namespace std; bool x[MAXNUM]; int M,n,r=0,w[MAXNUM]; void sumofsub(int s,int k,int r){ //左子树 x[k]=1; if (s+w[k]==M){ for(int i=1;i<=k;i++) printf("%d",x[i]); printf("\n"); } else if (s+w[k]+w[k+1]<=M) sumofsub(s+w[k],k+1,r-w[k]); //右子树 if (s+r-w[k]>=M&&s+w[k+1]<=M){ x[k]=0; sumofsub(s,k+1,r-w[k]); } } int main(){ printf("input n=? "); scanf("%d",&n); printf("input M=? "); scanf("%d",&M); printf("input w[]=?\n"); for(int i=1;i<=n;i++) { printf("w[%d]=",i); scanf("%d",&w[i]); } for(i=1;i<=n;i++) r=r+w[i]; w[n+1]=r; sumofsub(0,1,r); return 0; }