6
(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,8\rbrace\$ and \$n=6\$, you could take the following subcollections to get \$k=3\$:
- \$T_1=\lbrace1,1,2,2\rbrace\$
- \$T_2=\lbrace3,3\rbrace\$
- \$T_3=\lbrace6\rbrace\$
And the remaining elements \$\lbrace3,5,8\rbrace\$ are not used. However, there is a way to get \$k=4\$ separate subcollections:
- \$T_1=\lbrace1,2,3\rbrace\$
- \$T_2=\lbrace1,5\rbrace\$
- \$T_3=\lbrace3,3\rbrace\$
- \$T_4=\lbrace6\rbrace\$
This leaves \$\lbrace2,8\rbrace\$ unused. There is no way to do this with 5 subcollections1, 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:
- the maximal number of subcollections \$k\$; or
- 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\$.
It makes the program even slower, but
Œ!ŒṖ€§Ẏċ€Ṁ
saves a byte. – Dennis – 2018-10-30T12:51:43.237Oh, that was an oversight, thanks! – Jonathan Allan – 2018-10-30T13:35:31.863