算法 - 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

Nous écrivons du code plus court via 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

Supposons que le problème répond aux hypothèses suivantes :

1. Les éléments de la liste peuvent être réutilisés

2. Tant que la combinaison est inférieure ou égale à la limite supérieure, elle est acceptable, même si elle est bien inférieure à la limite supérieure voire nulle

Les lois suivantes sont violentes :

# 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 auxquelles j'ai répondu : Python-QA