# Python program to find all possible ways an integer num can be expressed as sum of integers between 1 and lim

This is a Python program that finds all possible ways a positive integer num can be expressed a sum of a number of integers between 1 and lim (including both ends).

There is no limit on the number of integers, duplicates are allowed, same elements in different order is considered different.

The output is a nested dictionary. Each key is a possible integer, each key in the nested dictionary is a possible integer in the series formed by the keys of the parent dictionaries in the previous levels that allows or makes the series sum to num.

From any last level keys, through the keys in the parent dictionaries, to the first level parent key, the sum of such a series is always num.

The Code

def partition_tree(num: int, lim: int) -> dict:
"""take a positive integer num and a positive integer lim,
calculate all possible ways integer num can be expressed as,
a summation of integers between 1 and lim, returns a tree"""
d = dict()
if any(not isinstance(i, int) for i in (num, lim)):
raise TypeError('The parameters of this function should be ints')
if any(i <= 0 for i in (num, lim)):
raise ValueError('The parameters should be both greater than 0')
def worker(num: int, lim: int, dic: dict) -> None:
for i in range(1, lim+1):
n = num - i
if n:
dic.setdefault(i, dict())
worker(n, lim, dic[i])
else:
dic.update({i: 0})
break
worker(num, lim, d)
return d


Example output:

def partition_tree(num: int, lim: int) -> dict:
"""take a positive integer num and a positive integer lim,
calculate all possible ways integer num can be expressed as,
a summation of integers between 1 and lim, returns a tree"""
d = dict()
if any(not isinstance(i, int) for i in (num, lim)):
raise TypeError('The parameters of this function should be ints')
if any(i <= 0 for i in (num, lim)):
raise ValueError('The parameters should be both greater than 0')
def worker(num: int, lim: int, dic: dict) -> None:
for i in range(1, lim+1):
n = num - i
if n:
dic.setdefault(i, dict())
worker(n, lim, dic[i])
else:
dic.update({i: 0})
break
worker(num, lim, d)
return d

import json
print(json.dumps(partition_tree(6, 3), indent=4))


Output:

{
"1": {
"1": {
"1": {
"1": {
"1": {
"1": 0
},
"2": 0
},
"2": {
"1": 0
},
"3": 0
},
"2": {
"1": {
"1": 0
},
"2": 0
},
"3": {
"1": 0
}
},
"2": {
"1": {
"1": {
"1": 0
},
"2": 0
},
"2": {
"1": 0
},
"3": 0
},
"3": {
"1": {
"1": 0
},
"2": 0
}
},
"2": {
"1": {
"1": {
"1": {
"1": 0
},
"2": 0
},
"2": {
"1": 0
},
"3": 0
},
"2": {
"1": {
"1": 0
},
"2": 0
},
"3": {
"1": 0
}
},
"3": {
"1": {
"1": {
"1": 0
},
"2": 0
},
"2": {
"1": 0
},
"3": 0
}
}


I came up with this in under 2 minutes and made it work in one try. I made this for use in my project to generate pseudowords, more specifically to calculate all possible ways a given word length num can be achieved using chunks of lengths 1 to lim.

How is the performance, coding style and memory consumption of my code (try partition_tree(18, 6), something like this can be in common use)? How can it be improved?

• So just want to confirm. The nested dictionaries represent a tree, where each root-to-leaf path has a path sum equal to the target, namely num? For completeness, the root can be thought of as having a value of zero; all other nodes have non-zero values; node values don't have to be unique. Oct 20, 2021 at 15:35
• worker(num, lim, dic) populates the input dictionary dic with a tree whose root-to-leaf paths each sum to num s.t. each node in the tree has a value, v, 1 <= v <= lim. Oct 20, 2021 at 15:46
• Btw, do you actually need to have all the different partitions or just the number of possibles partitions? Oct 21, 2021 at 9:17

## Recursion Improvements

In your problem, you end up calling the same recursive function multiple times. For example for partition_tree(6, 3) calls worker(2, 3, d) many many times albeit with updated dictionaries. This ends up costing you quite a bit of performance. You could avoid recomputing the same combinations by using memoization. Meaning you would save the outputs of your previous calls.

Python's functools makes it incredibly easy to implement memoization with the @lru_cache decorator:

@lru_cache(maxsize=None)
def worker(*args):
...


If we're to save calls to the function, we can't be passing around dictionaries or prefixes. It has to be a pure function. And limit doesn't change within the partition tree and therefore it doesn't need to be passed around either. So let's remove those arguments and do the updating ourselves:

from functools import lru_cache

def partition_tree_lru(num: int, lim: int) -> dict:
"""take a positive integer num and a positive integer lim,
calculate all possible ways integer num can be expressed as,
a summation of integers between 1 and lim, returns a tree"""

if any(not isinstance(i, int) for i in (num, lim)):
raise TypeError('The parameters of this function should be ints')
if any(i <= 0 for i in (num, lim)):
raise ValueError('The parameters should be both greater than 0')

@lru_cache(maxsize=None)
def worker(num: int) -> dict:
working_dict = {}
for i in range(1, lim+1):
n = num - i
if n:
working_dict[i]=worker(n)
else:
working_dict[i]=0
break
return working_dict

return worker(num)


Improvement:

function [partition_tree_lru]((50, 50)) finished in 1 ms
function [partition_tree]((20, 10)) finished in 570 ms


Note : if 'you're going to be calling the partition_tree multiple times for different inputs it would be worth moving the worker function definition to the outer scope so that the cache persists between calls.

In terms of code structure, here are my suggestions:

1. Move d = dict() to after the argument checks, so that you only create the dictionary if the inputs are valid.

2. The if/else statements inside the for loop can be removed:

        for i in range(1, lim+1):
n = num - i
if n:
dic.setdefault(i, dict())
worker(n, lim, dic[i])
else:
dic.update({i: 0})
break


becomes:

        for i in range(1, min(num, lim+1)):
n = num - i
dic.setdefault(i, dict())
worker(n, lim, dic[i])
if num <= lim:
dic.update({num: 0})

3. Additionally, dic.setdefault(i, dict()) has two modes. One for when the input key doesn't exist and one for when it does exists. I believe that within your code you're only ever hitting the latter mode (key doesn't exist), so dic.setdefault(i, dict()) can be replaced with dic[i] = dict().

4. Lastly, dic.update({num: 0}) can be replaced with dic[num] = 0 which would prevent you from creating the {num: 0} dictionary input to dic.update.

With all those changes, the code becomes:

def partition_tree(num: int, lim: int) -> dict:
"""take a positive integer num and a positive integer lim,
calculate all possible ways integer num can be expressed as,
a summation of integers between 1 and lim, returns a tree"""
if any(not isinstance(i, int) for i in (num, lim)):
raise TypeError('The parameters of this function should be ints')
if any(i <= 0 for i in (num, lim)):
raise ValueError('The parameters should be both greater than 0')
d = dict()
def worker(num: int, lim: int, dic: dict) -> None:
for i in range(1, min(num, lim+1)):
n = num - i
dic[i] = dict()
worker(n, lim, dic[i])
if num <= lim:
dic[num] = 0
worker(num, lim, d)
return d


I ran this code on your input:

import json
print(json.dumps(partition_tree(6, 3), indent=4))


and it produced the same output as your code.

In terms of code readability, I would suggest renaming d and dic to tree or something that indicates that the dictionaries represent a tree. I would also suggest renaming num to target or target_sum or just sum_ -- if take this suggestion, also consider renaming lim to max_num or max_; i to num; and n to new_target or new_target_sum or new_sum_ as appropriate. Also consider renaming worker to dfs since that's basically what it is doing and dfs is more descriptive than worker.

With some of the readability changes, the code looks like this:

def partition_tree(target_sum: int, max_num: int) -> dict:
"""take a positive integer num and a positive integer lim,
calculate all possible ways integer num can be expressed as,
a summation of integers between 1 and lim, returns a tree"""
if any(not isinstance(i, int) for i in (target_sum, max_num)):
raise TypeError('The parameters of this function should be ints')
if any(i <= 0 for i in (target_sum, max_num)):
raise ValueError('The parameters should be both greater than 0')
tree = dict()
def worker(target_sum: int, max_num: int, tree: dict) -> None:
for num in range(1, min(target_sum, max_num+1)):
new_target_sum = target_sum - num
tree[num] = dict()
worker(new_target_sum, max_num, tree[num])
if target_sum <= max_num:
tree[target_sum] = 0
worker(target_sum, max_num, tree)
return tree


This code still produces the same output as your original code.

• @@Xeнεi Ξэnвϵς, one more thing I noticed after writing my answer is that the dictionaries consist of sequential keys, starting from 1. It should make sense as we iterate over i from 1 creating items with i as the keys. All that to say that it should be possible to use lists instead of dicts to represent this tree structure and in fact shouldn't be too hard to make the switch. In general, I would think list access and memory consumption is better than dict's, so making that switch would probably improve things. Oct 20, 2021 at 16:35

I can't see why there is an upper limit. The size of the list can never exceed the function input number. So there is always a limit. And also as the summation numbers become larger, the list size becomes smaller. So there are no problems with removing the limit parameter. The code will not run forever when given a limit.

Perhaps you have some special case for limiting the summation numbers. I don't know, but it seems like this function has limited usefulness as a general function, and is checking to many things for no reason.

I can imagine that if I was using this function I would always provide a limit that is equal to the target sum. Because I would want a function to return all possibilities.

I guess there could be specific cases where a limit is required, but I would trim to that outside of the function. Perhaps the limiter might be useful for numbers in the billions. Still I wonder about time of completing the task or whether the code samples about will reach recursion limits. I know they will in the billions.

So my question is: why limit your function?

I say this, because I came here looking to find all sets of summations to an integer. But I had no need for limiting these summation numbers. And I couldn't think of a case where I would want to do that. The question must be a special case and not a general multi-purpose function. I think the special properties should be removed from code samples to make this generally useful to people looking for such code.