How to find the numbers that their sum equal to a given number?-CodePudding

This seems like a repost but it's not. Most people asked for the pair numbers. I need all numbers, not just two. Like n0 n1 n2 n3 n4 ... n100=x And also, each number must be lower than the number comes before him. For example for 8 output must be:

There are 5:
7 1
5 3
6 2
5 2 1
4 3 1

In here you can see 5>3 and 6>2 and vice versa. I came so close with this code. I found this on stackoverflow, and then improved it to according to my needs. However I tested it on a super computer, that if you give 200 to this, it says it's wrong. I just don't get it how could this be wrong? Please can someone help me improve this? With my pc it takes a lot of time. Give this 50, and it will still take hours. Here is my code:

from itertools import combinations
def solution(N):
    array=[]
    counter=0
    for i in range(N):
        if(i==0):
            continue
        array.append(i)
    for K in range(N):
        for comb in combinations(array, K):
            if sum(comb) == N:
                counter =1
                #print(comb) uncomment this if you like, it prints pairs.
    return counter  

res=solution(50)
print(res)

By the way, can I do it without itertools at all? Maybe it causes problems.

CodePudding user response：

I think I may have found a solution, I will share it and maybe you can check with me if it is correct :) I assumed that all numbers must be smaller than N.

To start, I am not so sure your code is necessarily wrong. I think it produces the right answers but maybe you should consider what is happening and why your code takes so long. Currently, you are checking for all combination of sums, but by iterating in another way you can exclude many possibilities. For example, suppose my goal is to find all sums that result in a total of 8. Suppose I now have a sum of 6 5 = 11. Currently, you are still checking all other possibilities when adding other numbers (i.e. 6 5 4 and 6 5 3 etc etc), but we already know they all will be >8, hence we do not even have to compute them.

As a solution we can start with the highest number smaller than our goal, i.e. 7 in our example. Then we will try all combinations with numbers smaller than this. As soon as our sum gets bigger than 8, we do not follow the trail further. This sounds a lot like recursing, which is how I currently implemented it.

To get an idea (I hope it is correct, I haven't tested it extensively):

def solution(goal, total_solutions=0, current_sum=0.0, current_value=None):
    if current_value is None:
        current_value = goal

    # Base condition
    if current_sum >= goal:
        if current_sum == goal:
            return total_solutions   1
        return total_solutions

    for new_value in range(current_value - 1, 0, -1):
        total_solutions = solution(
            goal, total_solutions, current_sum   new_value, new_value
        )
    return total_solutions


res = solution(8)
print(res)  # prints 5

So as an answer to your question, yes you can do it with itertools, but it will take a long time because you will be checking a lot of sums of which you do not really need to check.

I compared this program with yours and it produces the same output up until N=30. But then your code really starts to blow up so I won't check further.

CodePudding user response：

The Answer you're looking for is in the post : programming challenge: how does this algorithm (tied to Number Theory) work?

The classical method start taking some time at the 100th step but the use of memoization also called dynamic programming reduces the complexity drastically and allows your algorithm to compute at the 4000th step without taking any time at all.