The sum of some parts

Question

Challenge

Given a list of keys and values, and a target n, return all sets of keys where the sum of their values equals or exceeds n.

Input

Input will be like this:

[["Part 1", 20], ["Part 2", 15], ["Part 3", 14.75], ["Part 4", 3]], 30

Input consists of a list with keys (which can be any kind of string) and values (which can be any kind of decimal). Also, a number n is supplied as the target.

You may take these inputs in any format you like, in any order etc. It needs to support strings, numbers (with decimal precision and possibly negative).

The target might be positive, negative or zero. The list will always contain at least 1 KV-pair.

Each key is guaranteed to be unique. Each value <> 0. Different keys can have the same value. It is not guaranteed that a list holds a satisfactory combination.

Output

The expected output is a list of lists with all keys that have a combined value >=n. Each set that manages to satisfy this condition needs to be shown in a clearly distinguishable group, for example by separating them with brackets or newlines.

Sample output for the above input:

Part 1, Part2
Part 1, Part 3
Part 1, Part2, Part 3
Part 1, Part2, Part 4
Part 1, Part3, Part 4
Part 1, Part2, Part 3, Part 4
Part2, Part 3, Part 4

Note that each combination needs to be unique. The output doesn't need to be sorted, but part 1, part 2 is considered a duplicate of part 2, part 1 and should not be shown twice.

Additional rules

• Standard loopholes are forbidden
• Answer must be a full program or a function, not a snippet or a REPL-entry.
• code-golf, shortest answer in bytes wins.

Answer 1

05AB1E, 10 bytes

æʒø`O²‹_i,

Try it online!

Explanation

æ           # compute powerset of input
 ʒ          # filter out falsy values (we don't actually filter, it just saves a byte)
  ø         # zip into a list of keys and a list of values
   `        # push separately to the stack
    O       # sum values
     ²‹_i   # if not less than input_2
         ,  # print list of keys

Answer 2

Mathematica, 45 43 bytes

^{Saved 2 bytes due to alephalpha.}

Keys/@Cases[Subsets@#,a_/;Tr@Values@a>=#2]&

Anonymous function. Takes a list of rules (e.g., {"Part 1"->20,"Part 2"->15}) and a number as input and returns a list of lists of strings as output.

Answer 3

Japt, 15 14 12 bytes

Saved 2 bytes thanks to @obarakon

à f_xŨVÃm®g

Test it online! Output is a nested array, but it's rather hard to tell so the -R flag has been added to put each item on its own line.

Explanation

 à f_  xÅ  ¨ VÃ m®   g
Uà fZ{Zxs1 >=V} mmZ{Zg}
                         // Implicit: U = input array, V = input number
Uà                       // Take all combinations of U.
   fZ{        }          // Filter to only the combinations Z where this is true:
      Zxs1               //   The sum of each [item of Z]'s item at index 1
           >=V           //   is greater than or equal to V.
                m        // Map each combination in the result by
                 mZ{  }  //   mapping each array Z in that to
                    Zg   //     the first item in Z.
                         // This replaces each key-value pair with its key.
                         // Implicit: output result of last expression

An interesting thing to note is the use of Å (or s1 ) instead of g1 . s1 on an array simply returns everything but the first item. Since each array only has two items (a key and a value), this returns an array containing the value. x then uses JS's native coercion to convert this into a number, and on an array containing one number, this happens to return that number.

Answer 4

JavaScript (ES6), 127 123 bytes

Takes the list l and the target n in currying syntax (l)(n). Returns an array of arrays.

l=>n=>l.reduceRight((p,c)=>[...p,...p.map(x=>[c,...x])],[[]]).filter(x=>x.map(x=>s+=x[1],s=0)&&s>=n).map(x=>x.map(x=>x[0]))

Demo

let f =

l=>n=>l.reduceRight((p,c)=>[...p,...p.map(x=>[c,...x])],[[]]).filter(x=>x.map(x=>s+=x[1],s=0)&&s>=n).map(x=>x.map(x=>x[0]))

console.log(
  f([["Part 1", 20], ["Part 2", 15], ["Part 3", 14.75], ["Part 4", 3]])(30)
)

Answer 5

Haskell, 60 bytes

n#l=[map fst=<<e|e<-mapM(\p->[[],[p]])l,sum(map snd=<<e)>=n]

Usage example: 3 # [("Part 1",1), ("Part 2",1.5),("Part 3",2)] -> [["Part 2","Part 3"],["Part 1","Part 3"],["Part 1","Part 2","Part 3"]].

Try it online!

How it works:

      mapM(\p->[[],[p]])l         -- turn every element p from the input list l
                                  -- into a list [[],[p]], i.e. [<empty list>, <singleton list p>]
                                  -- and make a list of all combinations there by
                                  -- picking either [] or [p]
                                  -- e.g. [1,2] -> [[[],[]], [[],[2]], [[1],[]], [[1],[2]]] 
    e<-                           -- keep all elements e from this list where
          sum(map snd=<<e)>=n     -- the second elements of the pairs are >= n
[map fst=<<e |         ]          -- and extract the first elements of the pairs from it

Answer 6

R, 97 bytes

function(l,v){z=c()
k=combn
for(i in 1:length(l))z=c(z,lapply(k(l,i,,F)[k(l,i,sum)>=v],names))
z}

This is an anonymous function which takes the input in as a named list of values l (where the names are the parts) and a value v, and returns a list of vectors of names. Returns a list with value NULL if no matches are found.

The function combn(x,m)generates all elements of x taken m at a time with some options to simplify and aggregate. Hence the code iteratively generates the subsets of size i, k(l,i,,F), subsets those whose sum k(l,i,sum) is at least v, and then applies the names function to to each of those to extract the part names.

A different input scheme might lead to golfier code.

Try it online!

Answer 7

PHP, 134 bytes

function f($a,$n){$r=$n>0?[]:[[]];if([$k,$v]=each($a)){unset($a[$k]);$r=f($a,$n);foreach(f($a,$n-$v)as$t){$t[]=$k;$r[]=$t;}}return$r;}

Test it online.