6
\$\begingroup\$

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

\$\endgroup\$
3
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ It makes the program even slower, but Œ!ŒṖ€§Ẏċ€Ṁ saves a byte. \$\endgroup\$ – Dennis Oct 30 '18 at 12:51
  • \$\begingroup\$ Oh, that was an oversight, thanks! \$\endgroup\$ – Jonathan Allan Oct 30 '18 at 13:35
1
\$\begingroup\$

Jelly, 17 bytes

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

Try it online!

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

\$\endgroup\$
1
\$\begingroup\$

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)
\$\endgroup\$
0
\$\begingroup\$

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!

\$\endgroup\$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.