AOJ-1335 : Equal Sum Sets

Equal Sum Sets | Aizu Online Judge

n,k,sという３つの数字が与えられ、ある正の整数の組の合計が s になる組の数を求める。例えば、n=9以下の範囲で, k=3個の数字の組を対象に合計値がs=23になる組の数を求める場合は, {6, 8, 9} の１つである。但し、{3, 5, 9} と {5, 9, 3}のような組を同じ組として考える。

k の値が固定ならば、k重ループで全探索すれば良いだけだが、今回の場合は変化するので、bitを使った方法で解きました。1≦n≦20までなので計算量的には対した事がないのでbitを使って全探索します。現在のbitの1の数がk個の時に計算して、Sの値と同じならカウントします。

//http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1335

#include<iostream>
#include<map>
#include<vector>
#include<algorithm>
#include<cmath>
#include<climits>
#include<ctime>
#include<cstring>
#include<numeric>

#define ALL(v) (v).begin(),(v).end()
#define REP(i,p,n) for(int i=p;i<(int)(n);++i)
#define rep(i,n) REP(i,0,n)
#define dump(a) (cerr << #a << "=" << (a) << endl)
#define DUMP(list) cout << "{ "; for(auto nth : list){ cout << nth << " "; } cout << "}" << endl;

using namespace std;

int main()
{
	int N,K,S;
	while(cin >> N >> K >> S && N)
	{
		int ans=0;
		rep( bit, 1<<N )
		{
			if(__builtin_popcount(bit)!=K){ continue; }	
			int res=0;
			REP( n, 1, N+1 ){
				if( bit&1<<(n-1) ){ res+=n; }
			}
			if(res == S){ ans++; }
		}
		cout << ans << endl;
	}

	return 0;
}