Find unique sums to add to total (using only positive integers above 0)

Pep Sakdoek 0
Viewed 32

In the long run this will be used to find groups of words that spell another. (For crosswords)

But for now I just want to know some kind of generalized algorithm to calc the ways to get to a number using sums.

So lets say I have a 6 letter word, the only possible way to "create" that word from sub words would be words of length 5,4,3,2,1 (and I guess the word and word anagrams of that word):

6 = 6 
6 = 5 + 1
6 = 4 + 2
6 = 4 + 1 + 1
6 = 3 + 3
6 = 3 + 2 + 1
6 = 3 + 1 + 1 + 1
6 = 2 + 2 + 2
6 = 2 + 2 + 1 + 1
6 = 2 + 1 + 1 + 1 + 1
6 = 1 + 1 + 1 + 1 + 1 + 1

So I want code to generate me this in an array in python, so I can go look for words of combinations of lengths. I may want to exclude 1 letter words & same length words, but since there is just a max of 26 (and in English only I and A, and maybe if you include slang U) I don't think it'll make it too complex.

This doesn't need to be too optimized since usually like 15 is the highest I will go (I might even just type it all out and then I have it pre-solved, but it's going to be a fair amount for 15.

algorithm python
1 Answers

Here is a recursive solution to your question. We basically check all possible sum combinations until we find a valid one, then add it to our list of sums.

def find_sums(n):
    sums = []
    all_sums = []
    find_sums_helper(n, n, sums, all_sums)
    return all_sums

def find_sums_helper(n, n_max, sums, all_sums):
    if n == 0:
        all_sums.append(sums)
        return
    
    for i in reversed(range(1, min(n, n_max) + 1)):
        find_sums_helper(n - i, i, sums + [i], all_sums)

print(find_sums(6))

Output:

[[6], [5, 1], [4, 2], [4, 1, 1], [3, 3], [3, 2, 1], [3, 1, 1, 1], [2, 2, 2], [2, 2, 1, 1], [2, 1, 1, 1, 1], [1, 1, 1, 1, 1, 1]]
JRose0
Related