Seeking Substantial Subcollections

Question

(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 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\$.}

Answer 1

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

Answer 2

Jelly, 17 bytes

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

Try it online!

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

Answer 3

05AB1E, 9 8 bytes

œ€.œOQOZ

Port of @JonathanAllan's Jelly answer.

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)

Answer 4

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!