Ghilas BELHADJ Ghilas BELHADJ - 3 months ago 17
Python Question

Combinations of restricted set of integers

How to generate the list of combinations with

allowed_ints
that sums to
goal
?

Examples:

allowed_ints=[1,2], goal=4
combinations = [[1,1,1,1],[1,1,2],[2,1,1],[2,2],[1,2,1]]

allowed_ints=[5, 6], goal=13
combinations = []


What I've made so far don't works.

def combinations(allowed_ints, goal):
if goal > 0:
for i in allowed_ints:
for p in combinations(allowed_ints, goal-i):
yield [i] + p
else:
yield []

print list(combinations([1, 2],3))
[[1, 1, 1], [1, 1, 2], [1, 2], [2, 1], [2, 2]] # not what I want

Answer

Using you function try this:

def combinations(allowed_ints, goal):
    if goal > 0:
        for i in allowed_ints:
            for p in combinations(allowed_ints, goal-i):
                if sum([i] + p) == goal:
                    yield [i] + p
    else:
        yield []

print list(combinations([1, 2],3))

Outputs:

[[1, 1, 1], [1, 2], [2, 1]]