1564:Sum It Up

keyword

BruteForce　C++

概要

正の数Tとn(<12)個の数字が与えられる。和がTになる組合せを全て列挙する問題。
サイズが小さいのでBruteForce。重複を取り除くためにset< vector > とか使ってるけど0msでAC。

int main(){
    int mask, i, ns[15], n, m, t, sum;
    vector<int> tmp;
    set< vector<int> > ss;

    while(scanf("%d%d",&n,&t)){
        if(n==0 && t==0) break;
        ss.clear();
        printf("Sums of %d:\n", n);
        REP(i,t)scanf("%d",ns+i);
        sort(ns, ns+t, greater<int>());
        REP(mask,(1<<t)){
            sum = 0;
            REP(i,t)if(mask & (1<<i)) sum += ns[i];
            if(sum == n){
                tmp.clear();
                REP(i,t)if(mask & (1<<i)){
                    tmp.PB(ns[i]);
                }
                ss.insert(tmp);
            }
        }

        if(ss.empty()) printf("NONE\n");
        else{
            for(__typeof(ss.rbegin()) it = ss.rbegin(); it!=ss.rend(); it++){
                REP(i,SZ(*it)-1) printf("%d+",(*it)[i]);
                printf("%d\n",it->back());
            }
        }
    }

    return 0;
}