3

Number range is: 1 to 100

I wish to print out every unique combination between 1 and 100 whose sum equals 100 and finally a count of such combinations For example:

[1,99]
[1,2,97]
[1,2,3,4,5,85]

So, I need two things:

  1. print each valid combination
  2. return a final count of the number of such combinations

Here is what I have tried so far with no success:

count = 0
def get_count(target, data_range, current_sum):    
    global count    
    for num in data_range:        
        current_sum += num    
        if current_sum > target:
            break  
        elif current_sum == target:
            count += 1    
            current_sum = 0
        elif current_sum < target: 
            get_count(target, range(num + 1, 101), current_sum)
    return count
get_count(target = 100, data_range = range(1,101), current_sum = 0)
2
  • 1
    I diagree this is an exact dupe. It can be reduced to the linked question, but in here - you have an extra restriction. The given set of numbers is [1,2,..,100] - and not an arbitrary set.
    – amit
    Aug 5, 2013 at 7:06

1 Answer 1

0

This code does not print combinations.

def memoized(f):
    cache = {}
    def wrapper(*args):
        if args not in cache:
            cache[args] = f(*args)
        return cache[args]
    return wrapper

def get_count(target):
    @memoized
    def f(target, cur):
        if target < 0: return 0
        if target == 0: return 1
        return sum(f(target - n, n + 1) for n in range(cur, target + 1))
    return f(target, 1)

print(get_count(100))

Not the answer you're looking for? Browse other questions tagged or ask your own question.