解题思路:n个数随意组合,共有2的n次方种组合。设可以到达x的方法有m中,如果缺少了元素 arr[i] ,m=0 ,那么arr[i]就是不可缺少了。 我们用数组f[n] 表示到达 n 的方法有 f[n] 中,数组g[n] 表示在缺少元素 arr[i] 的情况下,到达n的方法,哎,我们就可以用f[n]不断地求出g[i]了。这样就有:
#include <iostream> #include <algorithm> #include <cstdlib> #include <cstring> #include <cstdio> #include <cmath> #define N 10000+10 using namespace std; int arr[N],f[N],g[N]; int main() { int n,x,i,j; while(~scanf("%d%d",&n,&x)) { for(i=0; i<n; i++) scanf("%d",&arr[i]); memset(f,0,sizeof(f)); f[0] = 1; //当f[i]遍历到 arr[j] = i 时他要加1,就是加他本身 for(i=0; i<n; i++) for(j=x; j>=arr[i]; j--) f[j] += f[j-arr[i]]; // f[0] = 1 , 就用到这了。 // for(i=0; i<=x; i++) // printf("%d ",f[i]); // printf("\n"); int stak[N],top = 0; for(i=0; i<n; i++) { memset(g,0,sizeof(g)); for(j=0; j<=x; j++) { if(j < arr[i]) //这时候到达j的情况里可没有arr[i]这个元素的功劳。 g[j] = f[j]; else g[j] = f[j] - g[j-arr[i]];//为什么不是f[j] - f[j-arr[i]]呢? 因为 g[j-arr[i]]这个j-arr[i] 的数值仍然可能会有arr[i]的功劳啊。 } if(g[x] == 0) stak[top++] = arr[i]; } printf("%d\n",top); if(top != 0 ) { printf("%d",stak[0]); for(i=1; i<top; i++) printf(" %d",stak[i]); } printf("\n"); } return 0; }