# Seeking Substantial Subcollections

(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:

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 , 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 11  10 bytes

-1 Thanks to Dennis (use count to remove the need to tie atoms together with any quick)

Œ!ŒṖ€§Ẏċ€Ṁ


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?

Œ!ŒṖ€§Ẏċ€Ṁ - Link: list L, integer I
Œ!         - all permutations
ŒṖ€      - for €ach: all partitions (all ways to slice up each permutation)
§     - sum each (vectorises at depth 1, so this gets the sums of the parts of
-           each of the partitions for each permutation)
Ẏ    - tighten  (to get a list of the sums of the parts of each possible partition)
ċ€  - for €ach count occurrences of I
Ṁ - maximum

• It makes the program even slower, but Œ!ŒṖ€§Ẏċ€Ṁ saves a byte. – Dennis Oct 30 '18 at 12:51
• Oh, that was an oversight, thanks! – Jonathan Allan Oct 30 '18 at 13:35

# Jelly, 17 bytes

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


Try it online!

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

# 05AB1E, 9 8 bytes

œ€.œOQOZ


Try it online. NOTE: Extremely slow, so times out for most test cases beyond the size of 6..

Explanation:

œ           # All permutations of the (implicit) input-list
€.œ        # Take all partitions of each permutation
O       # Sum each
Q      # Check for each if it's equal to the (implicit) integer-input
O     # Then sum each
Z    # And take the maximum (implicitly flattens the list of lists)
# (and output implicitly)


# 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!