(thanks to @JonathanFrech for the title)

Challenge

Write a program or function that, given a collection of positive integers $S$ and a positive integer $n$, finds as many non-overlapping subcollections $T_1, T_2, ..., T_k$ of $S$ as possible, such that the sum of every $T_m$ is equal to $n$.

Example

Given $S=lbrace1,1,2,2,3,3,3,5,6,8rbrace$ and $n=6$, you could take the following subcollections to get $k=3$:

• $T_1=lbrace1,1,2,2rbrace$


• $T_2=lbrace3,3rbrace$


• $T_3=lbrace6rbrace$

And the remaining elements $lbrace3,5,8rbrace$ are not used. However, there is a way to get $k=4$ separate subcollections:

• $T_1=lbrace1,2,3rbrace$


• $T_2=lbrace1,5rbrace$


• $T_3=lbrace3,3rbrace$


• $T_4=lbrace6rbrace$

This leaves $lbrace2,8rbrace$ unused. There is no way to do this with 5 subcollections¹, so $k=4$ for this example.

Input

Input will be a collection of positive integers $S$, and a positive integer $n$. $S$ may be taken in any reasonable format: a comma- or newline-separated string, an actual array/list, etc. You may assume that $S$ is sorted (if your input format has a defined order).

Output

The output may be either:

1. the maximal number of subcollections $k$; or


2. any collection which has $k$ items (e.g., the list of subcollections $T$ itself), in any reasonable format.

Note that there is not guaranteed to be any subcollections with sum $n$ (i.e. some inputs will output 0, , etc.)

Test cases

n, S -> k
1, [1] -> 1
1, [2] -> 0
2, [1] -> 0
1, [1, 1] -> 2
2, [1, 1, 1] -> 1
3, [1, 1, 2, 2] -> 2
9, [1, 1, 3, 3, 5, 5, 7] -> 2
9, [1, 1, 3, 3, 5, 7, 7] -> 1
8, [1, 1, 2, 3, 4, 6, 6, 6] -> 2
6, [1, 1, 2, 2, 3, 3, 3, 5, 6, 8] -> 4
13, [2, 2, 2, 2, 3, 3, 4, 5, 5, 6, 8, 9, 9, 11, 12] -> 5
22, [1, 1, 2, 3, 3, 3, 3, 3, 4, 4, 4, 5, 6, 6, 7, 7, 7, 8, 9, 9, 10, 13, 14, 14, 17, 18, 18, 21] -> 10

Scoring

This is code-golf, so the shortest program in bytes in each language wins. Good luck!

^{1. Mini-proof: the $8$ is obviously useless, but when you remove it, the total sum of $S$ becomes $26$; therefore, it can only contain up to $4$ non-overlapping subcollections whose sums are $6$.}

Jelly, 17 bytes

Œ!ŒṖ€ẎŒP€Ẏ§;EɗƇẈṀ

Try it online!

Outputs $k$ if there is a $T$, $0$ otherwise. Very slow.

Jelly,  17  11 bytes

Œ!ŒṖ§=ɗ€§FṀ

A dyadic link accepting a list and an integer which yields the maximal count, $k$.

Try it online! Or see the test-suite -- it's too slow for the larger test cases :(

How?

Œ!ŒṖ§=ɗ€§FṀ - Link: list L, integer I
Ã…Â’! - all permutations
 € - for €ach:
 ɗ - last three links as a dyad - i.e. f(permutation, I)
 ŒṖ - partitions (all ways to slice up the permutation)
 § - sum each (vectorises at depth 1, so this gets the sums of the parts of
 - the partitions)
 = - equals? (==I) -> 1 if so 0 otherwise 
 § - sum each (vectorises at depth 1, so this gets the counts of parts equal to I
 - for each partition of each permutation) 
 F - flatten
 Ṁ - maximum

JavaScript (Node.js), 115 bytes

k=>f=([i,...s])=>i?Math.max(...[i,...s].map((_,j)=>(e[j]=~~e[j]+i,_=f(s),e[j]-=i,_))):e.filter(_=>_==k).length;e=

Try it online!