Given a sequence of numbers, print out all possible sets such that the sum is less than a number

Question

The problem has 3 inputs.

L: a list of all numbers

size: the size each set can be

max: the max sum amongst each set

The challenge is as follows:

Given L, size and max, construct as many sets from L such that the number of elements is size and the sum of each of the elements does not exceed max.

Examples:

func(L=[1,2,3,4], size=2, max=5) = [{1,2}, {1,3}, {2,3}, {1,4}]

Notice how each of the values in the outputted set are sum <= max.

func(L=[1,2,3,4], size=3, max=6) = [{1,2,3}]

func(L=[1,2,3,4], size=3, max=5) = [{}] or empty list, whichever you want

Note that in the set you cannot have duplicated items. ie: {2,1} = {1,2}

Constraints on inputs:

L: 0 or more elements

size: 0 <= size <= len(L)

max: 0 or more

If a list has 0 items, then always return the empty set.

If the size is 0, then always return the empty set.

If max is 0, it is possible that there are negative values in L, in which case the returned sets need not be empty.

Shorted bytes wins!

Answer 1

05AB1E, 6 bytes

.ÆêʒO@

Try it online!

Answer 2

Brachylog, 9 bytes

≥ᵗ⟨⟨⊇l⟩+⟩

Try it online!

Takes input as [[L,size],max] through the input variable and generates the output through the output variable.

Answer 3

Python 3, 82 79 bytes

lambda l,s,m:[i for i in __import__("itertools").combinations(l,s)if sum(i)<=m]

Try it online!

-3 bytes thanks to squid

Answer 4

Japt, 11 bytes

àV â fÈx §W

Try it

àV â fÈx §W     :Implicit input of array U=L and integers V=size & W=max
àV              :Combinations of U of length V
   â            :Deduplicate
     f          :Filter by
      È         :Function
       x        :  Sum
         §W     :  Less than or equal to W

Answer 5

R, 56 bytes

function(L,s,m,a=combn(L,s))unique(a[,colSums(a)<=m],,2)

Try it online!

Creates a matrix where each column is a subset of L of size s, and keeps those for which the sum is less than m. Output is a matrix, with each column corresponding to one allowable subset (if there is only one such subset, the output is a s×1 matrix and R will display it on one row instead by default).

Note that this fails for the edge case where L is empty. Handling that edge case as specified in the challenge takes 19 more bytes:

R, 75 bytes

function(L,s,m,a=combn(L,s))`if`(length(L),unique(a[,colSums(a)<=m],,2),{})

Try it online!

Answer 6

Gaia, 8 bytes

Σ⊂
euK↑⁇

Try it online!

Takes input as list, size, max sum on separate lines.

Answer 7

Jelly, 9 bytes

QœcS>¥Ðḟ⁵

Try it online!

Answer 8

Pyth, 15 bytes

{SMfgeQsT.PhQht

Try it online!

{SMfgeQsT.PhQhtQ  # (last Q implicit; Q = input)
         .P       # all permutations
           hQ     #   of Q[0]
             htQ  #           of length Q[1:][0] = Q[1]
   f              # filter those with lambda T:
     eQ           #   Q[-1]
    g             #          >=
       sT         #             sum(T)
 SM               # sort each element
{                 # deduplicate

Answer 9

Kotlin, 286 bytes

fun p(l:List<Int>,s:Int,m:Int){val r=MutableList(0){""}
val a=l.toSet().toList()
fun r(n:Int,b:Int,t:Int,u:List<Int>){if(n<1){if(t<=m)r.add(u.joinToString(",","{","}"))}else
for(e in b..a.size-1)r(n-1,e+1,t+a[e],u+listOf(a[e]))}
r(s,0,0,List(0){0})
println(r.joinToString(",","[","]"))}

Try it online!