题目链接：点击打开链接
题目大意：点击打开链接
解题思路：DFS + 剪枝 + 计数（若不计数 + 不剪枝都会TLE）。
AC 代码
#include<bits/stdc++.h> #include<cmath> #define mem(a,b) memset(a,b,sizeof a) #define ssclr(ss) ss.clear(), ss.str("") #define INF 0x3f3f3f3f #define MOD 1000000007 using namespace std; typedef long long ll; const int maxn=1e4+10; int n,m,f,len; int a[maxn], rs[maxn], cnt[150]; void dfs(int sum,int l) { if(f) return; // if(sum>m) return; // 1 if(m==sum) { for(int i=0;i<l;i++) printf("%d%c",rs[i],i==l-1?'\n':' '); f=1; return; } for(int i=0;i<len;i++) { if(cnt[a[i]]>0) { if(sum+a[i]>m) return; // 在这里剪枝比在 1 处剪枝效率好很多 cnt[a[i]]--; rs[l]=a[i]; dfs(sum+a[i],l+1); cnt[a[i]]++; } } } int main() { int t; scanf("%d%d",&n,&m); for(int i=0;i<n;i++) { scanf("%d",&t); // 最后一个测试点，卡这点，因为这会出现比如：1 1 1 2 3 4，而前三个 1 在cnt中分别都有三个，就重复计算了很多次 // if(t<=m) a[len++]=t, cnt[t]++; if(t<=m) { if(cnt[t]==0) a[len++]=t; cnt[t]++; } } sort(a,a+len); dfs(0,0); if(!f) puts("No Solution"); return 0; }
