Subset Sum with Exact Subset Size - Flipkart Online Assessment SDE Role IIIT Bhubaneswar

Problem Preview

"You are provided with a collection of items, each having a unique weight. A buyer wishes to purchase a set of these items, subject to two strict conditions set by the market rules: 1. The total weight of the chosen items must be exactly equal to a target weight $W$. 2. The buyer must choose exactly $N$ items. Given the available item weights, write a program to calculate the total number of distinct combinations (subsets) of exactly $N$ items that sum up to exactly $W$. ### **Input Format** * The first line consists of a single integer $W$, representing the target total weight. * The second line contains two space-separated integers, $N$ and $X$, where $N$ is the exact number of items the buyer must select, and $X$ is the total number of items available. * The third line contains $X$ space-separated integers representing the weights of the available items. ### **Output Format** * Print a single integer on a new line representing the total number of valid ways to choose exactly $N$ items that sum to $W$. ### **Constraints** * All $X$ weights are unique and given in strictly ascending order. * $0 < W \le 500$ * $0 < N \le 50$ * $0 < X \le 100$ --- ### **Sample Input 1** ```text 20 3 10 1 2 4 5 10 11 13 15 17 19 ``` ### **Sample Output 1** ```text 4 ``` **Explanation 1:** The target weight is $W = 20$, and the required number of items is $N = 3$. The 4 valid combinations of 3 items that sum to 20 are: * 1, 2, 17 * 1, 4, 15 * 2, 5, 13 * 4, 5, 11 --- ### **Sample Input 2** ```text 45 7 19 1 2 4 5 6 8 9 10 12 13 15 16 17 18 19 20 21 23 24 ``` ### **Sample Output 2** ```text 12 ``` **Explanation 2:** The target weight is $W = 45$, and the required number of items is $N = 7$. There are exactly 12 distinct subsets of 7 items from the given array that sum to 45 (e.g., {1, 2, 4, 5, 6, 8, 19}, {1, 2, 4, 5, 6, 9, 18}, etc.)."