AOJ 1335. Equal Sum Sets

12/1のチーム練習会にて解いた。

problem

要素数$k$の有限集合$X \subseteq \{ 1, 2, \dots, n \}$で$\sum X = s$なものはいくつあるか。

solution

愚直。$O(2^n n)$。

implementation

#include <cstdio>
#define repeat(i, n) for (int i = 0; (i) < int(n); ++(i))
using namespace std;

int main() {
    while (true) {
        int n, k, s; scanf("%d%d%d", &n, &k, &s);
        if (n == 0 and k == 0 and s == 0) break;
        int result = 0;
        repeat (x, 1 << n) if (__builtin_popcount(x) == k) {
            int acc = 0;
            repeat (i, n) if (x & (1 << i)) {
                acc += i + 1;
            }
            result += (acc == s);
        }
        printf("%d\n", result);
    }
    return 0;
}