算法 - python 给定一个正整数a和一个包含任意个正整数的 列表 b，求所有<=a 的加法组合

Question

例如，10,[1,2,3]

输出类似：
1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1
2 + 2 + 2 +2 + 2
3 + 3 + 3 + 2
3 + 2 + 2 + 2 + 1

注意：是小于等于，list 内的正整数有可能并不能正好等于 a.

Answer 1

We write shorter code through itertools.combinations_with_replacement:

def solve2(lst, bound):
    max_length = bound // min(lst)
    for n in range(1, max_length+1):
        for c in itertools.combinations_with_replacement(lst,n):
            if sum(c) <= bound:
                print('+'.join(map(str, c)))
            
solve2([1,2,3], 10)

Answer 2

Suppose this problem meets the following assumptions:

1. Elements in the list can be reused

2. As long as the combination can meet the requirement of being less than or equal to the upper limit, it is acceptable, even if it is far less than the upper limit or even zero

The following are the violent laws:

# code for python3

from itertools import combinations

def solve(lst, upperbound):
    candidates = []
    for n in lst:
        for count in range(upperbound//n):
            candidates.append(n)
    allcomb = set()
    for l in range(1, len(candidates)+1):
        for comb in combinations(candidates, l):
            if not comb in allcomb:
                allcomb.add(comb)
                if sum(comb) <= upperbound:
                    print('+'.join([str(n)for n in comb]))
        
solve([1,2,3], 10)

---

Questions I answered: Python-QA