Equal Sum Sets
InterviewTime limit3sMemory limit128 MB
Count subsets of {1..n} with exactly k elements that sum to s for each dataset.
- Level
Easy3 of 10
- Topics
- Dynamic programming, Combinatorics
- Solved
- No attempts yet
Problem
Consider sets of positive integers that are at most . All elements of a set are different, and the order of elements does not matter, so {3, 5, 9} and {5, 9, 3} are the same set.
Once the number of elements is fixed to and their sum to , few sets satisfy both conditions. For , and , the set {6, 8, 9} is the only one. In general there can be more than one. For , and , both {5, 8, 9} and {6, 7, 9} satisfy the conditions.
Write a program that counts the sets satisfying the given conditions.
Input
The input consists of several datasets. The number of datasets does not exceed 100.
Each dataset is one line holding the integers , and , separated by a space. Assume , and .
A line with three zeros marks the end of the input.
Output
For each dataset, print the number of sets satisfying the conditions on one line. Print no other characters.
The number of sets does not exceed .