Link Sub: http://www.spoj.com/PTIT/problems/P142SUME/
Người Gửi: Ok
- Problem:
Xét tất cả các tập hợp các số nguyên dương có các phần tử khác nhau và không lớn hơn số n cho trước. Nhiệm vụ của bạn là hãy đếm xem có tất cả bao nhiêu tập hợp có số lượng phần tử bằng k và tổng của tất cả các phần tử trong tập hợp bằng s? Các tập hợp là hoán vị của nhau chỉ được tính là một.
Ví dụ với n = 9, k = 3, s = 23, {6, 8, 9} là tập hợp duy nhất thỏa mãn.
Input
Gồm nhiều bộ test (<= 100 test).
Mỗi bộ test gồm 3 số nguyên n, k, s với 1 ≤ n ≤ 20, 1 ≤ k ≤ 10 và 1 ≤ s ≤ 155.
Input kết thúc bởi 3 số 0.
Output
Với mỗi test in ra số lượng các tập hợp thỏa mãn điều kiện đề bài.
Example:
Với mỗi test in ra số lượng các tập hợp thỏa mãn điều kiện đề bài.
Input
9 3 23
9 3 22
10 3 28
16 10 107
20 8 102
20 10 105
20 10 155
3 4 3
4 2 11
0 0 0
Output:
1
2
0
20
1542
5448
1
0
0
- Solution:
- Bài này số lượng n và k nhỏ ta có thể đệ quy quay lui sinh các trường hợp. - Xét tất cả các số từ [x, n] với mỗi số lựa chọn ta xét tiếp các số từ [x+1, n] cho số tiếp theo.... xét cho đến khi đủ k số. Nếu tổng thu được == s ta thực hiện đếm.