分析
这道题数据范围较小,看题目问题,可确定是一个dfs,每次要么走'-',要么走'+',时间复杂度
大概为O( ),可以小剪枝一下,如果当前加上所有的数如果都小于最后一个数,就不用搜了,
或者是减去后面所有数都大于最后的数,也不用再搜下去了
代码
//#pragma GCC optimize(3,"inline","Ofast","fast-math","no-stack-protector","unroll-loops") //#pragma GCC target("sse","sse2","sse3","sse4","avx","avx2","popcnt") /* (写点什么吧...) */ #include<bits/stdc++.h> #define R register #define ll long long #define inf INT_MAX using namespace std; const int N=22; const ll mod=1e9+7; int n,m,las,p; int a[N],sum[N]; char ans[N]; vector<string>q; inline void dfs(int now,int tot) { //剪枝 if(now==n) { if(tot==las) { p++; string s=""; for (int i=2;i<=m;i++) s+=ans[i]; q.push_back(s); } return ; } if(tot+sum[m]-sum[now-1]<las) return ; if(tot-(sum[m]-sum[now-1])>las) return ; ans[now]='-'; dfs(now+1,tot-a[now]); ans[now]='+'; dfs(now+1,tot+a[now]); } int main() { scanf("%d",&n);m=n-1; for (int i=1;i<n;i++) scanf("%d",&a[i]); scanf("%d",&las); for (int i=1;i<=m;i++) sum[i]=sum[i-1]+a[i]; dfs(2,a[1]); printf("%d\n",p); for (int i=0;i<p;i++) cout<<q[i]<<"\n"; return 0; }