All combinations that equals or exceed a given number

Question

It is different from the coin-changing problem link.

Given a dict x=[a:1,b:2,c:1,d:3,e:2], I need to calculate all possible combinations of the keys such that the sum of the values associated with those keys just exceeds or equals a given value, say 5. Just exceeding 5 means that if the selected elements are lower than 5, we can add one more element even if it exceeds 5 but once we exceed or equal 5, no more elements can be added.

There are two issues that are complicating my approach -

1. Note that some of the values are repeated-e.g. 1 and 2 each occurs twice and they need to be considered separately.
2. Ordering matters in this case.

Ordering matters too so [b,c,d], [b,d,c], [c,b,d], [c,d,b], [d,b,c], [d,c,b] are all included separately. Ideally ordering matters only when we are exceeding 5 and as long as the sum is exactly 5, ordering doesn't matter.

So some of the solution to the above question are [a,b,c,d] with sum 7, [a,b,c,e] with sum 6, [b,c,d] with sum 6, [d,e] with sum 5 etc.

How do I approach the problem. I was thinking of using the output from coin changing and then adding one element to each of the resulting lists, but that will not cover all the cases.

EDIT 1: A better way of framing the question might be to find all combinations such that the sum (i) equals 5 or (ii) just exceeds 5 as the sum until the second last element was less than 5 and therefore adding the last element made it greater than 5. Once we have 5 or >5, no additional elements will be added.

EDIT 2: Clarifying the ordering issue. To give a bit of context, the keys are devices and the values are the resources it needs. And the total resources available is 5. And the devices are allocated resources as per their keys i.e. the first key-value pair will be serviced first (sorted as per the key alphabetically). For b, it needs 2 but say only 1 resource is available - it will be assigned 1 and the remaining 1 will be assigned in the next run (spillover). So when the sum is exactly 5, the order doesn't matter as each gets whatever it wanted and there is no spillover to the next slot. E.g. ed and de means both get what they wanted so they should both be included. But for lists that exceed 5 just due to the addition of the last element, ordering matters as spillover will happen only for the last element. E.g. dce means d and c get 3 and 1 respectively, and e gets only 1 (with 1 spilling into next run). Similarly ced means c and d get 1 and 3 respectively, with spillover happening for d as it only gets assigned 1.

Answer 1

Updated Answer

More detail about the requirements have been added to the question. I think this version matches them. But the expected output structure was not specified, so this is a guess. It ends up with an array of results like this:

{initial: {a: 1, b: 2, c: 1}, last: {d: 3}}

or like this:

{initial: {b: 2, c: 1, e: 2}}

It does this by first finding all subsets of the initial values, together with their complements, using the function partitions. partitions (['a', 'b', 'c', 'd']) would have sixteen elements including [['a', 'b', 'd'], ['c']], [['b', 'd'], ['a', 'c']], and [[], ['a', 'b', 'c', 'd']].

Then, for each partition, if its sum of the left half is equal to the target we include it. If the sum is less than the target, we include a result for every value in the right half that brings us over the target.

Here's an implementation in Javascript:

// utility functions
const last = (xs) => 
  xs [xs .length - 1]

const partitions = (xs) => 
  xs .length === 0
    ? [[[], []]]
    : partitions (xs .slice (0, -1)) .flatMap (([p, q]) => [ 
        [[...p, last (xs)], q], 
        [p, [...q, last (xs)]] 
      ])

// helper function
const total = (xs) =>
  xs .reduce ((a, [k, v]) => a + v, 0)


// main function
const sumTo = (n, xs, parts = partitions (xs)) =>
  parts .flatMap (([incl, excl], _, __, t = total (incl)) => [
    ... (t == n ? [{initial: incl}] : []),
    ... (t < n
           ? excl .filter (([k, v]) => v + t > n) 
                  .map (e => ({initial: incl, last: [e]}))
           : []
        )
  ])


// public function
const subsetSum = (n, dict) =>
  sumTo (n, Object.entries (dict))
    .map (({initial, last}) => ({
      initial: Object .fromEntries (initial), 
      ... (last ? {last: Object .fromEntries (last)} : {})
    }))


// sample data
const dict = {a: 1, b: 2, c: 1, d: 3, e: 2}


// demo
console .log (subsetSum (5, dict))

.as-console-wrapper {max-height: 100% !important; top: 0}

We start with a trivial helper function, last, which simply selects the last element of an array. Then we have partition, already described above. Our main function is sumTo, which does the work described. Its inputs are the target number and a structure like [['a', '1], ['b', 2'], ['c', 1], ['d', 3], ['e', 2]], which is easy to derive from a dictionary but is easier to work with. It returns an object with two properties, something like {initial: [['a', 1], ['b', 2], ['c', 1]], last: [['d', 3]]}. Finally we have out public function subsetSum, which converts from the dictionary format to the input needed for sumTo and then converts the result back into the output format. This would be easy to fix to create whatever output format you need.

With a little formatting of the output, we can see our results more simply:

subsetSum  (5, dict)
  .map (({initial, last}) => 
      Object .keys (initial) .join ('') +
      (last ? '-' + Object .keys (last) .join ('') : '')
  )
//=> ["abc-d", "abc-e", "abe", "ab-d", "acd", "ace-b", 
//    "ace-d", "ad-b", "ad-e", "ae-d", "bce", "bc-d", 
//    "bd", "be-d", "cd-b", "cd-e", "ce-d", "de"]

This is likely ill-performant. I don't have a real sense of the likely growth patterns of the problem. But this algorithm is exponential in the size of the dictionary, and there's no way around it for this technique, as the subset problem at the heart of partitions has 2 ^ n results.

But it might be a starting point to compare with for other solutions.

Original Answer

If all orderings matter (and I'm confused by the details of that requirement), then this algorithm should do it, using a list of entries each with a key and a value:

if (n <= 0) or if our list of entries is empty,
  return a list containing only the empty string
otherwise return the concatenation of the following lists, one for each entry:
  a recursive call passing 
    - `n - value`
    - the list excluding the current entry,
  with each result being prepended with the current entry's key 

If you're comfortable with Javascript syntax, then this should work:

const excluding = (i) => (xs) =>
  [...xs .slice (0, i), ...xs .slice (i + 1)]

const sumTo = (n, xs) =>
  n <= 0 || xs.length == 0 
    ? ['']
    : xs .flatMap (
        ([k, v], i) => sumTo (n - v, excluding (i) (xs)) .map (r => k + r)
      )
  
const subsetSum = (n, dict) => 
  sumTo (n, Object .entries (dict))

const dict = {a: 1, b: 2, c: 1, d: 3, e: 2}

console .log (subsetSum (5, dict))

.as-console-wrapper {max-height: 100% !important; top: 0}

It's hard to imagine that order could be entirely irrelevant, since 'cde' should fit but 'dec' should not. But I don't understand the notion that order is only relevant when the total exceeds the target. Can you explain more fully?