all combinations of numbers 1-5 summing to <=9

Question

I need to find all combinations of 3 numbers 1-5 that sum to 9. Only 3 numbers from set=[1,2,3,4,5] can be used.

The issue now is I'm getting numbers above 5.

Any suggestions?

# arr - array to store the combination 
# index - next location in array 
# num - given number 
# reducedNum - reduced number  
def findCombinationsUtil(arr, index, num, 
                              reducedNum): 

    # Base condition 
    if (reducedNum < 0): 
        return; 

    # If combination is  
    # found, print it 
    if (reducedNum == 0): 

        for i in range(index): 
            print(arr[i], end = " "); 
        print(""); 
        return; 

    # Find the previous number stored in arr[].  
    # It helps in maintaining increasing order 
    prev = 1 if(index == 0) else arr[index - 1]; 

    # note loop starts from previous  
    # number i.e. at array location 
    # index - 1 
    for k in range(prev, num + 1): 

        # next element of array is k
        arr[index] = k; 

        # call recursively with 
        # reduced number 
        findCombinationsUtil(arr, index + 1, num,  
                                 reducedNum - k); 

# Function to find out all  
# combinations of positive numbers  
# that add upto given number. 
# It uses findCombinationsUtil()  
def findCombinations(n): 

    # array to store the combinations 
    # It can contain max n elements 
    arr = [0] * n; 


# find all combinations 
findCombinationsUtil(arr, 0, n, n);

It's been awhile since I've used Python (not since college) so I'm a little rusty. Any feedback is appreciated!

Possible duplicate of [Sum a list of numbers in Python](https://stackoverflow.com/questions/4362586/sum-a-list-of-numbers-in-python) — Matthew Gaiser, Oct 02 '19 at 00:09

blhsing · Accepted Answer · 2019-10-01T21:53:40.700

You can use a function that iterates through the values in the given sequence, and combine each of them with each of the combination returned from a recursive call with the target value deducted by the current value, and the target number reduced by 1, until the target number becomes 0:

def find_combinations(arr, target, num):
    if target >= 0 == num:
        yield []
    elif target > 0:
        for item in arr:
            for combination in find_combinations(arr, target - item, num - 1):
                yield [item, *combination]

so that:

for combination in find_combinations(range(1, 6), 9, 3):
    print(combination)

outputs:

[1, 1, 1]
[1, 1, 2]
[1, 1, 3]
[1, 1, 4]
[1, 1, 5]
[1, 2, 1]
[1, 2, 2]
[1, 2, 3]
[1, 2, 4]
[1, 2, 5]
[1, 3, 1]
[1, 3, 2]
[1, 3, 3]
[1, 3, 4]
[1, 3, 5]
[1, 4, 1]
[1, 4, 2]
[1, 4, 3]
[1, 4, 4]
[1, 5, 1]
[1, 5, 2]
[1, 5, 3]
[2, 1, 1]
[2, 1, 2]
[2, 1, 3]
[2, 1, 4]
[2, 1, 5]
[2, 2, 1]
[2, 2, 2]
[2, 2, 3]
[2, 2, 4]
[2, 2, 5]
[2, 3, 1]
[2, 3, 2]
[2, 3, 3]
[2, 3, 4]
[2, 4, 1]
[2, 4, 2]
[2, 4, 3]
[2, 5, 1]
[2, 5, 2]
[3, 1, 1]
[3, 1, 2]
[3, 1, 3]
[3, 1, 4]
[3, 1, 5]
[3, 2, 1]
[3, 2, 2]
[3, 2, 3]
[3, 2, 4]
[3, 3, 1]
[3, 3, 2]
[3, 3, 3]
[3, 4, 1]
[3, 4, 2]
[3, 5, 1]
[4, 1, 1]
[4, 1, 2]
[4, 1, 3]
[4, 1, 4]
[4, 2, 1]
[4, 2, 2]
[4, 2, 3]
[4, 3, 1]
[4, 3, 2]
[4, 4, 1]
[5, 1, 1]
[5, 1, 2]
[5, 1, 3]
[5, 2, 1]
[5, 2, 2]
[5, 3, 1]

This is great for all combos summing to 9! But I'm trying to find all <=9. So minimum value would be 3. — Owen Schifferli, Oct 01 '19 at 21:48

benvc · Answer 2 · 2019-10-02T02:53:41.790

Given the small range you are working with, you could just apply a bit of brute force with itertools.combinations_with_replacement. This approach does not yield every permutation of each combination, so if that is needed the other answer takes care of that for you (i.e. this approach yields (1, 1, 3) but not (1, 3, 1) or (3, 1, 1)).

from itertools import combinations_with_replacement

combos = [x for x in combinations_with_replacement(range(1, 6), 3) if sum(x) < 10]
print(combos)
# [(1, 1, 1), (1, 1, 2), (1, 1, 3), (1, 1, 4), (1, 1, 5), (1, 2, 2), (1, 2, 3), (1, 2, 4), (1, 2, 5), (1, 3, 3), (1, 3, 4), (1, 3, 5), (1, 4, 4), (2, 2, 2), (2, 2, 3), (2, 2, 4), (2, 2, 5), (2, 3, 3), (2, 3, 4), (3, 3, 3)]

all combinations of numbers 1-5 summing to <=9

2 Answers2