文章

金额查错(2011省赛)

金额查错1.png

深度优先搜索

#include<bits/stdc++.h>
using namespace std;
const long long int maxn=2e5+10;
long long int n,s,cnt=0,num;
long long int bijiao[maxn];
long long int a[maxn];
long long int ans[maxn];
long long int check(long long num){
    long long int i;
    for(i=0;i<num;i++){
        if(ans[i]!=bijiao[i])
        return 1;
    }
    return 0;
}
void find(long long int loc,long long int sum){
    long long int i;
    if(loc==n) return ;
    //考虑当前物品 
    ans[cnt]=a[loc];
    sum+=a[loc];
    cnt++;
    if(sum==s){
        if(num==0||num!=cnt||(num==cnt&&check(num)==1)){//没有重复 
            for(i=0;i<cnt;i++){
                cout<<ans[i]<<' ';
            }cout<<endl;
        }
        num=cnt;
        for(i=0;i<num;i++){
            bijiao[i]=ans[i];
        }
    }else {
        find(loc+1,sum);
        sum-=a[loc];
    }
    cnt--;
    //不考虑当前物品
    find(loc+1,sum);
    return ; 
}
int main()
{
    long long int ws,i,sum=0;
    cin>>ws>>n;
    for(i=0;i<n;i++) {
        cin>>a[i];
        sum+=a[i];  
    }
    sum-=ws;
    s=sum;
    sort(a,a+n);
    find(0,0);
    return 0;
}
License:  CC BY 4.0