Python: find shortest list of numbers which when added would be a specific number

Question

Just like the title says: The function to write has 2 parameters, the first is a number, the second a list of numbers:

example: (7, [5,3,4,7]) The Python function to write should return a list of numbers that when added would lead to '7' for example [3,4] or [4,3] or [7]

I wrote a Python function that actually works (see below bestSum()), but it only returns 1 working combination and I wish that someone could help edit it so it will return ALL possible "good" combinations. Then I could select the shortest one.

The recursive Python function is using a binary tree to go down by substracting a number from the list to the main number (substracting the same number is ok). If last node has 0 in it then that is a winner but if comes out as negative then that it is an impossible combination and should be dropped.

So instead of just returning, let say [4,3], it would return instead: ([3,4], [4,3], [7]) OR at least help me change the looping so it will not stop after it find the first working combination.

def bestSum(nb, intlist, res=[[], []]):
    if (nb == 0):
        res[0] = True
        return res
    if (nb < 0):
        res[0] = False
        return res

    for i in intlist:
        remainder = nb - i
        res = bestSum(remainder, intlist, res)
        if (res[0] == True):
            res[1].append(i)
            res[0] = True
            return res
    res[0] = False
    return res

For now these 2 lines of code

res = bestSum(7, [5,3,4,7])
print("Shortest Result list is = ", res[1])

will return:

Shortest Result list is = [4, 3]

(Which is not really the shortest, it should be [7])

ATTENTION: This is NOT the same as the coin change problem since that coin problem also includes cents and always has a solution, and here we do not. So here there is not always a solution for example in the case of (7, [4,5]) there is no combination of 4 and 5 that can be added to lead to 7.

THANKS

Bad news, your code actually doesn't work. Example `bestSum(7, [2,1])` yields `[True, [1, 2, 2, 2]]`. You have to pass only the sublist that wasn't tested yet. — mozway, Dec 30 '21 at 06:19
@mozway, I am not sure what you mean by "it does not work" ? If you add these numbers in the result-list, such as 1+2+2+2 = 7 , so it works. I guess I am missing your point, can you please clarify/elaborate. Thank you. — MMEL, Dec 30 '21 at 06:46
You only have one time `2` in the list can you use it 3 times? (If yes, let me know if some day you go into the banking business, I'll be your first customer :p) — mozway, Dec 30 '21 at 06:50
Do you want only one of the `shortest` combination or `all` possible combination? — Jay, Dec 30 '21 at 06:52
@mozway, I am sorry for any confusion, but part of the example as I said in the text "(substracting the same number is ok)" , so the same number can be used several times. — MMEL, Dec 30 '21 at 07:00
@Jay, YES that is exactly it, I wish to edit my function so that it will return the shortest combination, I just dont know how to make the recursion to continue looping for all combinations until it finds the shortest one. — MMEL, Dec 30 '21 at 07:00
@MMEL then it looks like a [Knapsack problem](https://en.m.wikipedia.org/wiki/Knapsack_problem) with replacement. — mozway, Dec 30 '21 at 07:10
@mozway, wow thanks, I have to agree that it kinda looks like it, though, I would say that mine is a more simple version since all items only have 1 property, which is their value, whereas in the Knapsack case they have 2 properties, weight and value. — MMEL, Dec 30 '21 at 07:27
This is instead a [subset sum](https://en.m.wikipedia.org/wiki/Subset_sum_problem) problem. — Karl Knechtel, Dec 30 '21 at 08:25

Karl Knechtel · Answer 1 · 2021-12-30T08:11:26.430

The underlying question is:

I have a recursive algorithm. When I make one or more recursive calls, I want to collect the results from those recursive calls, and use them to produce the result for this level of the recursion. (Simplest case: I want a list of all the recursive results.) How can I accomplish this simply?

It is much easier to reason about recursive algorithms when we don't rely on any side effects or mutable data structures. Modifying lists - especially when they are default parameters being used as a cache - quickly becomes a headache. Even if we get some immutable data back from the recursive calls (say, a tuple) and want to combine those results, it's often rather awkward. (It can be difficult to remember, for example, that some leaf result ought to be () or a singleton tuple, rather than None or a particular element value.)

The way around this, that I recommend, is to use a recursive generator instead. I wish to show several approaches, however, in order to explain some general technique for recursive algorithms.

Let's first consider the trivial example of listing all the nodes in a tree, in depth-first order:

def all_nodes_at(root):
    # If this is a leaf node, then `root.children` is empty;
    # so the loop will simply not run and nothing is yielded.
    for child in root.children:
        yield from all_nodes_at(child)
    yield root # include the current node, after all nodes underneath.

# To see the results, we need to iterate over the generator in some way:
tree_nodes = list(all_nodes_at(tree_root))

Compare that to the approach using tuples:

def all_nodes_at(root):
    result = ()
    for child in root.children:
        result = result + all_nodes_at(child)
    return result + (root,)

tree_nodes = all_nodes_at(tree_root)

Seems considerably uglier to me. Using list caches:

def all_nodes_at(root, cache=[]):
    for child in root.children:
        cache.extend(all_nodes_at(child))
    cache.append(root)
    return cache

tree_nodes = all_nodes_at(tree_root)

Oof. Not only are we forced to return a value that we don't actually use in the recursion (so that we get a result at the top level), but it breaks if we want to use it more than once. "Oh, that's fine, we'll just clear the cache first." Really? You want to document that users need to do all_nodes_at.__defaults__[0].clear() before calling the function? Surely it would be better not to default the parameter. Better if it weren't a default parameter and the user supplied the initial cache:

def dump_all_nodes_at(root, cache):
    for child in root.children:
        cache.extend(all_nodes_at(child))
    cache.append(root)

tree_nodes = []
dump_all_nodes_at(tree_root, tree_nodes)

At least this is reusable, and we don't have to play silly games with the return value (in fact, we don't have to return at all). But it's a really awkward interface now.

You can see why I generally prefer the recursive generator.

Let's apply the technique to the problem of finding all subsets with a given sum. But first, we need to think clearly about the recursive algorithm. We don't actually want, at a given step of the algorithm, to try each element. Why? Because if we only try the first element, then other elements will be handled by later steps in the recursion. Sure, that means we don't get every possible ordering of a given result set; but we can fix that later with e.g. itertools.permutations if it really matters. (Also, I'm pretty sure your approach doesn't prevent using the same element more than once.)

The simple definition is as follows: a subset with the given sum either includes the first element, or it does not. Our subsets consist of

elements from the previous levels of the recursion that we decided to include;
possibly the current element;
elements from a recursive call on the remaining elements.

What we'll do is prepend the current element to results from the recursive call where appropriate (i.e., the one where we recursively called with a smaller target sum). The other elements will get automatically prepended as we bubble back through the recursion.

Thus:

def subsets_with_sum(values, target):
    if target < 0:
        # There are no solutions, so bail out.
        return
    if not values:
        # Nesting the check like this allows for zeros in `values`.
        if target == 0:
            # We have reached the trivial solution.
            yield ()
        # No current element, therefore no more solutions.
        return
    # Otherwise, we recurse twice, yielding sub-results.
    # First, some useful renaming
    this_value, *other_values = values
    for subset in subsets_with_sum(other_values, target - this_value):
        yield (this_value,) + subset # prepend and yield it back
    # `yield from` is sugar for iterating and yielding each result directly.
    yield from subsets_with_sum(other_values, target)

Let's test it:

>>> list(subsets_with_sum([5,4,3,7], 7))
[(4, 3), (7,)]
>>> list(subsets_with_sum(range(10), 10))
[(0, 1, 2, 3, 4), (0, 1, 2, 7), (0, 1, 3, 6), (0, 1, 4, 5), (0, 1, 9), (0, 2, 3, 5), (0, 2, 8), (0, 3, 7), (0, 4, 6), (1, 2, 3, 4), (1, 2, 7), (1, 3, 6), (1, 4, 5), (1, 9), (2, 3, 5), (2, 8), (3, 7), (4, 6)]

Rather than iterate over the results to pick the shortest ones, try filtering the results that you yield back, recursively. This is left as an exercise. Hint: if you are applying that filtering recursively, then everything you get back from the recursive call must be the same length - do you see why? So, there's a simple question of whether to use the results from each of the two recursive calls. You should be able to think of a simple rule for this. But you will need to *inspect* the results from the recursive calls, so maybe you had better go back to a tuple-stitching approach... — Karl Knechtel, Dec 30 '21 at 08:08
If you *want* to be able to use the same value multiple times, then simply replace `subsets_with_sum(other_values, target - this_value)` with `subsets_with_sum(values, target - this_value)` - so that we consider `this_value` when trying to make up the rest of the sum. Of course, we don't do that to the other recursive call, since that creates a useless infinite recursion. — Karl Knechtel, Dec 30 '21 at 08:24
Thank you very much for this solution, I am going to test it now, though I have a clarification to ask. Why the use of tuples in the result-set and particular reason, why not just regular lists? — MMEL, Dec 30 '21 at 08:32
In order to encourage side-effect-less thinking. We don't *want* mutability here. That said, as a pragmatic matter, you may find it more performant to use lists when you have to concatenate multiple results. The size of the underlying sequences might matter a bit too. It's been a while since I did any real performance testing on this kind of thing. — Karl Knechtel, Dec 30 '21 at 08:33
Based on @MMEL's comments(`bestSum(7, [2,1]) yields [True, [1, 2, 2, 2]]`), his combinations can have same value in `values` used multiple times in a valid combination, so its not a "subset sum" problem. But you can use a similar idea and instead use list, and for loops instead of using the sets and `this_value, *other_values = values` to iterate over each value in `values` during each recursion. — Jay, Dec 30 '21 at 08:56
@KarlKnechtel, as far as finding the shortest one, why not using a simple "min(item, key=len)" on the final list returned instead of modifying the recursive function? Would editing the recursive function lead to better O(complexity) or just more clarity? — MMEL, Dec 30 '21 at 09:03
@KarlKnechtel, wish you could tell me what to change in my function to make my recursive function to return all combination and not just the first one found. Why would that be great is because that function is closer of the way I think and I also worked on on it for so long that I wish to know , what in my code could be changed in order to return all combinations... — MMEL, Dec 30 '21 at 09:31
"why not using a simple "min(item, key=len)" on the final list returned instead of modifying the recursive function?" Because it means accumulating fewer/smaller intermediate results. I'm not sure if that makes for an actual big-O improvement, but it should definitely be a pragmatic one. — Karl Knechtel, Dec 30 '21 at 13:57
@Karl, Itried your recursive solution with this call res_list = list(subsets_with_sum([2,1], 7)) and the result came out totally empty, it came out as [ ], how is that possible? It should have returned at least these 2 tuples (2,2,2,1) and (1,1,1,1,1,1) How is that possible, what did I miss here? — MMEL, Jan 05 '22 at 03:36
"what did I miss here?" You missed a careful understanding of the part where I explained the derivation, and you missed my second follow-up comment. I wrote the code specifically not to allow using the same element more than once, and a small modification is required to allow that. — Karl Knechtel, Jan 06 '22 at 23:00

Jay · Accepted Answer · 2021-12-31T05:23:38.913

Based on the comments in the question, we can pick the same element in the intlist multiple times to form a combination that sums up to the given target.

Iterative solution

Here we step through the different values in the intlist and build a new combination summing up to a given sum, and then adding new numbers in it.

def bestSum(target, intlist):
    # initialize the dp dict
    dp = {} # dp[combinationSum] = combination
    for num in intlist:
        dp[num] = [num]
    # max steps we would need to arrive at a valid combination(if it exists) would be
    # the combination containing only the min element in the intlist
    # e.g. for target = 20 and intlist = [2,7], if we don't find a valid combination within
    # 10 steps(all 2's), no valid answer would exist
    for step in range(target//min(intlist) + 1):
        for combinationSum, combination in dp.copy().items(): # avoid modifying the dict while itrating
            for i in intlist:
                newSum = combinationSum + i
                if newSum == target:
                    # since we are taking a step one at a time, the first sum being equal to target
                    # will guarantee a shortest combination
                    return combination + [i]
                if newSum > target:
                    # skip if newSum if over target(skip adding additional entries into dp to improve perf)
                    continue
                if not dp.get(newSum):
                    # if the dp already has an non-zero length list in it = its length is going to be
                    # at least equal to new combination length or lower, so we don't need to overwrite it
                    dp[newSum] = combination + [i]

target, intlist = 20, [5,3,4,7]
print(bestSum(target, intlist))

prints

[5, 5, 5, 5]

for simplicity, here's what we would have in dp at each step for intlist = [5,3,4,7] and target of 20 -

Step : 0 - dp: {3: [3], 4: [4], 5: [5], 7: [7]}
Step : 1 - dp: {3: [3], 4: [4], 5: [5], 6: [3, 3], 7: [7], 8: [5, 3], 9: [5, 4], 10: [5, 5], 11: [4, 7], 12: [5, 7], 14: [7, 7]}
Step : 2 - dp: {3: [3], 4: [4], 5: [5], 6: [3, 3], 7: [7], 8: [5, 3], 9: [5, 4], 10: [5, 5], 11: [4, 7], 12: [5, 7], 13: [5, 5, 3], 14: [7, 7], 15: [5, 5, 5], 16: [5, 4, 7], 17: [5, 5, 7], 18: [4, 7, 7], 19: [5, 7, 7]}
Step : 3 - dp: {3: [3], 4: [4], 5: [5], 6: [3, 3], 7: [7], 8: [5, 3], 9: [5, 4], 10: [5, 5], 11: [4, 7], 12: [5, 7], 13: [5, 5, 3], 14: [7, 7], 15: [5, 5, 5], 16: [5, 4, 7], 17: [5, 5, 7], 18: [4, 7, 7], 19: [5, 7, 7], 20: [5, 5, 5, 5]}

Recursive Solution

If you want to stick with the recursive approach, you can make small changes to your original code to make it return all the combinations summing to the required target.

First of all, we don't need to make the function return True/False, instead we can just return None in case there is no valid combination that sums to the target value.

We want to collect all the combinations which sums to the required value so instead of returning the function on finding a valid combination what we should do is save it somewhere where we can access it later.

combinations = []
def bestSum(target, intlist, res=[]):
    if (target == 0):
        # found a valid combination
        combinations.append(res)  # collect the current combinations - THIS is what you were looking for
        return
    if (target < 0):
        return
    for i in intlist:
        remainder = target - i
        bestSum(remainder, intlist, res + [i])

target, intlist = 20, [5, 4, 3, 7]
bestSum(target, intlist)
print(combinations, len(combinations))

now all your combinations which sum to the target are written to combinations now, but this has a few problems..

Above code prints -

[[5, 5, 5, 5], [5, 5, 4, 3, 3], [5, 5, 3, 4, 3], [5, 5, 3, 3, 4], [5, 5, 3, 7], [5, 5, 7, 3], [5, 4, 5, 3, 3], [5, 4, 4, 4, 3], [5, 4, 4, 3, 4], [5, 4, 4, 7], [5, 4, 3, 5, 3], [5, 4, 3, 4, 4], [5, 4, 3, 3, 5], [5, 4, 7, 4], [5, 3, 5, 4, 3], [5, 3, 5, 3, 4], [5, 3, 5, 7], [5, 3, 4, 5, 3], [5, 3, 4, 4, 4], [5, 3, 4, 3, 5], [5, 3, 3, 5, 4], [5, 3, 3, 4, 5], [5, 3, 3, 3, 3, 3], [5, 3, 7, 5], [5, 7, 5, 3], [5, 7, 4, 4], [5, 7, 3, 5], [4, 5, 5, 3, 3], [4, 5, 4, 4, 3], [4, 5, 4, 3, 4], [4, 5, 4, 7], [4, 5, 3, 5, 3], [4, 5, 3, 4, 4], [4, 5, 3, 3, 5], [4, 5, 7, 4], [4, 4, 5, 4, 3], [4, 4, 5, 3, 4], [4, 4, 5, 7], [4, 4, 4, 5, 3], [4, 4, 4, 4, 4], [4, 4, 4, 3, 5], [4, 4, 3, 5, 4], [4, 4, 3, 4, 5], [4, 4, 3, 3, 3, 3], [4, 4, 7, 5], [4, 3, 5, 5, 3], [4, 3, 5, 4, 4], [4, 3, 5, 3, 5], [4, 3, 4, 5, 4], [4, 3, 4, 4, 5], [4, 3, 4, 3, 3, 3], [4, 3, 3, 5, 5], [4, 3, 3, 4, 3, 3], [4, 3, 3, 3, 4, 3], [4, 3, 3, 3, 3, 4], [4, 3, 3, 3, 7], [4, 3, 3, 7, 3], [4, 3, 7, 3, 3], [4, 7, 5, 4], [4, 7, 4, 5], [4, 7, 3, 3, 3], [3, 5, 5, 4, 3], [3, 5, 5, 3, 4], [3, 5, 5, 7], [3, 5, 4, 5, 3], [3, 5, 4, 4, 4], [3, 5, 4, 3, 5], [3, 5, 3, 5, 4], [3, 5, 3, 4, 5], [3, 5, 3, 3, 3, 3], [3, 5, 7, 5], [3, 4, 5, 5, 3], [3, 4, 5, 4, 4], [3, 4, 5, 3, 5], [3, 4, 4, 5, 4], [3, 4, 4, 4, 5], [3, 4, 4, 3, 3, 3], [3, 4, 3, 5, 5], [3, 4, 3, 4, 3, 3], [3, 4, 3, 3, 4, 3], [3, 4, 3, 3, 3, 4], [3, 4, 3, 3, 7], [3, 4, 3, 7, 3], [3, 4, 7, 3, 3], [3, 3, 5, 5, 4], [3, 3, 5, 4, 5], [3, 3, 5, 3, 3, 3], [3, 3, 4, 5, 5], [3, 3, 4, 4, 3, 3], [3, 3, 4, 3, 4, 3], [3, 3, 4, 3, 3, 4], [3, 3, 4, 3, 7], [3, 3, 4, 7, 3], [3, 3, 3, 5, 3, 3], [3, 3, 3, 4, 4, 3], [3, 3, 3, 4, 3, 4], [3, 3, 3, 4, 7], [3, 3, 3, 3, 5, 3], [3, 3, 3, 3, 4, 4], [3, 3, 3, 3, 3, 5], [3, 3, 3, 7, 4], [3, 3, 7, 4, 3], [3, 3, 7, 3, 4], [3, 3, 7, 7], [3, 7, 5, 5], [3, 7, 4, 3, 3], [3, 7, 3, 4, 3], [3, 7, 3, 3, 4], [3, 7, 3, 7], [3, 7, 7, 3], [7, 5, 5, 3], [7, 5, 4, 4], [7, 5, 3, 5], [7, 4, 5, 4], [7, 4, 4, 5], [7, 4, 3, 3, 3], [7, 3, 5, 5], [7, 3, 4, 3, 3], [7, 3, 3, 4, 3], [7, 3, 3, 3, 4], [7, 3, 3, 7], [7, 3, 7, 3], [7, 7, 3, 3]] 123

A whopping 123 combinations just for a small target of 20. If you go through the list of combinations, you will notice that the combinations include all permutations of a given valid combination resulting in this bloated size. The code also has to do additional work to derive all those combinations.

What can we do to avoid these duplicates? Sorting comes to the rescue; if we ensure that each valid combination is always sorted then there cannot be a permutation of the same combination in final combinations. How can this be leveraged in the code?

combinations = []
def bestSum(target, intlist, combination=[]):
    if (target == 0):
        # found a valid combination
        combinations.append(combination)
        return
    if (target < 0):
        return
    for i in intlist[::-1]:
        # each combination will be in ascending order
        # while i is in descending order here, so if last element in my
        # combination is greater than i, we can break the loop to stop
        # additional work, and make sure that all the combinations are unique
        if combination and combination[-1] > i:
            break
        remainder = target - i
        bestSum(remainder, intlist, combination + [i])

target, intlist = 20, [5, 4, 3, 7]
bestSum(target, sorted(intlist)) # sort list of values
print(combinations, len(combinations))

this outputs

[[5, 5, 5, 5], [4, 4, 5, 7], [4, 4, 4, 4, 4], [3, 5, 5, 7], [3, 4, 4, 4, 5], [3, 3, 7, 7], [3, 3, 4, 5, 5], [3, 3, 3, 4, 7], [3, 3, 3, 3, 4, 4], [3, 3, 3, 3, 3, 5]] 10

Now, we don't have any permutations in our combinations! And we can easily get all the shortest/longest combinations as needed from the combinations.

But as pointed out by @karl in his answer, the interface for this looks quite bad, and we should actually use recursive generators to make the interface cleaner. Which would look something like this -

def bestSum(target, intlist, combination=[]):
    if (target == 0):
        # found a valid combination
        yield combination
    if (target < 0):
        return
    for i in intlist[::-1]:
        if combination and combination[-1] > i:
            break
        remainder = target - i
        yield from bestSum(remainder, intlist, combination + [i])

target, intlist = 20, [5, 4, 3, 7]
intlist.sort()
targetCombinations = list(bestSum(target, intlist))
targetCombinations.sort(key=lambda x: len(x))
print("One of the shortest combination - ", targetCombinations[0])

Returning only one of the shortest path using recursion - this is not possible using just the return and use of a single recursion function since once we return a value, we won't be able to keep on searching through the remaining combinations. So a way to get around this would be to wrap your recursion function in another function and make that return the shortest combination you come across after going through all combinations or use a global variable (I would avoid going the global variable way) or pass a variable by reference to the original function.

def shortestCombinationSum(target, intlist, combination=[]):
    shortest = None
    def bestSum(target, intlist, combination):
        nonlocal shortest
        if (target == 0 and (not shortest or len(combination) < len(shortest))):
            # found a valid combination which is shorter
            shortest = combination
            return
        if (target < 0):
            return
        for i in intlist[::-1]:
            if combination and combination[-1] > i:
                break
            remainder = target - i
            bestSum(remainder, intlist, combination + [i])
    bestSum(target, intlist, combination)
    return shortest

target, intlist = 20, [5, 4, 3, 7]
print(shortestCombinationSum(target, sorted(intlist)))

Although this makes the function look weird, the interface for the shortestCombinationSum is fairly clean. Another alternative could've been making shortest as a global variable and then keep updating it, we would not have to wrap the function in another function in that case, but we will have to clear the value of the global variable in case we are calling the function over and over again with different sets of inputs.

I would still recommend the iterative solution over the recursive solution above because given an intlist of size n, the tree you have in your diagram would be an n-ary tree, having n branches on each node starting from target at the top. The iterative solution would be similar to a level order traversal in the n-ary tree and would stop when it reaches the level where it finds the solution. While the recursive solution would be DFS over the tree and it would need to go through each and every combinations(pruning duplicate permutations) of the n-ary tree.

Thank you, your solution works very well. Have you tried to derive the O(complexity) of this non-recursive approach? — MMEL, Dec 30 '21 at 08:56
In the worst-case no. of steps would be `target/min(intlist)`, during each step, we are iterating over all the values in the `intlist` and at times, we would be doing `dp[newSum] = combination + [i]` which can be `O(n)` in worst case(if `intlist` contains 1), so the bound would be `O(mn^2)` where `m` is the length of `intlist` and `n` is the target. But in most cases, it would run much faster if we find an answer early and avg length of each combination would be smaller than `n`. And we are only updating the `dp[combinationSum]` value once. — Jay, Dec 30 '21 at 09:10
The worst-case space complexity can be `O(n^2)`, when `intlist` has 1, where `n` is `target`. — Jay, Dec 30 '21 at 09:11
We can also short circuit some edge cases at the beginning of the `bestSum ` function, `if target is in intlist: return [target]` and `if target < min(intlist): return None`, remove any entries in `intlist` which are larger than `target`, etc. for further optimizations. — Jay, Dec 30 '21 at 09:14
I agree with the O(n^2) and I also dont think the short-circuit elements would do much for performance since these cases are real exceptional, though they would make the code more elegant and definitely more complete. — MMEL, Dec 30 '21 at 09:34
@MMEL added a recursive solution based on your attempt in question. — Jay, Dec 30 '21 at 11:42
Thank you for adding this version. That recursive solution works very well, I was wondering why the use of the reverse list [ : :-1] since you are already doing a sort on it? Also, I was wondering if, using a recursive solution, it would be possible to only send the shortest as final return ? — MMEL, Dec 30 '21 at 19:19
If we don't use the `intlist[::-1]` on sorted `intlist` we would need to do the `continue` in the condition which checks if the `combination[-1] > i` instead of `break`, so iterating over reversed list there would lead to some performance improvement, as we would be breaking early. Also added a recursive solution which returns the one of the shortest combinations. — Jay, Dec 31 '21 at 05:24
I did run your second recursive solution, the one avoiding duplicates and the one using the "intlist[::-1]". It works well, though does not appear entirely accurate as some combinations, although not duplicates are not returned, for example [5,5,5,5] is not in the combinations of items returned. Is there a reason for that? do you consider [5,5,5,5] a duplicate? — MMEL, Jan 03 '22 at 09:42
`shortest` in the second recursive solution is storing a single combination, so once the first shortest combination gets stored there, it will not be updated because we will not update shortest if `len(combination) < len(shortest)`. If you want all the combinations of shortest length then you can make `shortest` a list of combinations and when length of a new combination = length of shortest combination, append the new combination to the list. — Jay, Jan 03 '22 at 16:34

score 0 · Answer 3 · answered Dec 30 '21 at 09:00

This is a simple one :

import itertools as it

# create all possible route

def create_permutation(data):
    
    final = []

    for k in range(1, len(data) + 1):
        
        temp = list(it.permutations(data, k))

        final.extend(temp)
        

    return final

# find best sum in equal to num

def best_sum(subs, num, _min = True):

    final = []

    for i in range(len(subs)):

        temp_sums = sum(subs[i])

        if temp_sums == num:
            final.append(subs[i])

    if not final:
        return None


    # if only wants minimum then sort by length then return first
    if _min:
        return sorted(final, key = lambda x : len(x))[0]
    return final
    
    

def main(data, num):

    subs = create_permutation(data)
    
    result = best_sum(subs, num, False)

    print("Best === ", result)



data = [5, 3, 4, 7, 2]
num = 7

main(data, num)

Python: find shortest list of numbers which when added would be a specific number

3 Answers3

Iterative solution

Recursive Solution