# 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