What is the logic for discovering all possible numbers that add up to the requested number?

Asked

Viewed 96 times

6

But note that the number on the left is always higher than the number on the right. I’ve tried several ways, but I don’t think I understand the logic to create an algorithm that does this so I always fail in numbers greater than 8.

Example: 8 decomposed would be
8
7 + 1
6 + 2
6 + 1 + 1
5 + 3
5 + 2 + 1
5 + 1 + 1 + 1
4 + 4
4 + 3 + 1
4 + 2 + 2
4 + 2 + 1 + 1
4 + 1 + 1 + 1 + 1
3 + 3 + 2
3 + 2 + 2 + 1
3 + 2 + 1 + 1 + 1
3 + 1 + 1 + 1 + 1 + 1
2 + 2 + 1 + 1 + 1 + 1
2 + 1 + 1 + 1 + 1 + 1 + 1
1 + 1 + 1 + 1 + 1 + 1 + 1 + 1

logic
  • 2

    This page is aimed at specific programming problems. Take a look at Tour

  • 7

    @Augustovasques to my view this is a specific problem of programming and is valid on the site.

  • @Andersoncarloswoss and Turista suggestion to analyze: Find all possible subsets that sum up to a Given number, of the ones I found seemed to me the simplest to understand and perhaps even more efficient than the others, I have not made a benchmark yet, but nor is this the need here, when there is time I will try to post the results of the performance tests.

1 answer

1

These are numerical partitions. One possible solution is to find the combinations and remove duplicates.

def sum_to_n(n):
    b, mid, e = [0], list(range(1, n)), [n]
    splits = [d for i in range(n) for d in combinations(mid, i)]
    list1 = [map(sub, chain(s, e), chain(b, s)) for s in splits]
    return set([tuple(sorted(t, reverse=True)) for t in list1])

Browser other questions tagged logic

You are not signed in. Login or sign up in order to post.