# 50014. Selection

## Problem Description

Given a set of $n$ positive integers and another positive integer $K$, is there a way to pick a subset of size exactly $S$ from the set so that the sum of the numbers in the subset is exactly $K$? For example, the set is $\lbrace 1, 2, 3, 3, 2\rbrace$, $K$ is $7$, $S$ is $3$, then the answer is yes, since we can find a subset ${2, 2, 3}$ whose sum of elements is $7$. However if $S$ is $2$ then we cannot find any solution.

You need to implement the following function as described above.

1int subset(int numbers[], int n, int K, int S);


• 10pt. S is 2.
• 10pt. S is 3.
• 10pt. n is 4.
• 60pt. S is between 4 and 7, and n is no more than 10.
• 10pt. S is between 1 and n, and n is no more than 30.

## Hint

To solve the last subtask you need to notice that if the sum of the numbers you selected is already more than $K$, you should stop the recursion.

## Source codes

### main.c

12345678910111213#include <stdio.h>#include "subset.h" int main() {    int n, K, S;    while (scanf("%d %d %d", &n, &K, &S) == 3) {        int A[128];        for (int i = 0; i < n; i++)            scanf("%d", &A[i]);        printf("%d\n", subset(A, n, K, S));    }    return 0;}


### subset.h

1int subset(int numbers[], int n, int K, int S);


### subset.c

12345#include "subset.h" int subset(int numbers[], int n, int K, int S){    // Fill your code in here.}


## Sample Input 1

20 51 261 56 93 78 77 16 61 72 25 65 67 67 71 19 95 96 25 4 56 42


## Sample Output 1

0


## Sample Input 2

20 61 266 60 90 82 72 97 54 21 31 20 59 29 31 45 57 46 46 40 15 8


## Sample Output 2

1