给定一个数字列表，您可以将多少种不同的方法添加到一起来获得总和S？
例：
list = [1,2]
S = 5
1) 1+1+1+1+1 = 5
2) 1+1+1+2 = 5
3) 1+2+2 = 5
4) 2+1+1+1 = 5
5) 2+2+1 = 5
6) 1+2+1+1 = 5
7) 1+1+2+1 = 5
8) 2+1+2 = 5
答案= 8
这是我尝试过的，但它只输出3作为答案
lst = [1, 2]
i = 1
result = 0
while i <= 5:
s_list = [sum(comb) for comb in combinations_with_replacement(lst, i)]
for val in s_list:
if val == 5:
result += 1
i+= 1
print(result)
但是，这输出三个。我相信它输出三个因为它没有考虑你可以添加数字的不同顺序。任何关于如何解决这个问题的想法。
这个问题应该适用于更大的数据：但是，我给出了这个简单的例子来给出一般的想法。
同时使用itertools.combinations_with_replacement和permutations：
import itertools
l = [1,2]
s = 5
res = []
for i in range(1, s+1):
for tup in itertools.combinations_with_replacement(l, i):
if sum(tup) == s:
res.extend(list(itertools.permutations(tup, i)))
res = list(set(res))
print(res)
[(1, 2, 2),
(2, 2, 1),
(1, 1, 2, 1),
(1, 2, 1, 1),
(2, 1, 1, 1),
(1, 1, 1, 2),
(2, 1, 2),
(1, 1, 1, 1, 1)]
print(len(res))
# 8
如何使用动态编程？我相信它更容易理解，并且可以轻松实现。
def cal(target, choices, record):
min_choice = min(choices)
if min_choice > target:
return False
for i in range(0, target+1):
if i == 0:
record.append(1)
elif i < min_choice:
record.append(0)
elif i == min_choice:
record.append(1)
else:
num_solution = 0
j = 0
while j < len(choices) and i-choices[j] >= 0:
num_solution += record[i-choices[j]]
j += 1
record.append(num_solution)
choices = [1, 2]
record = []
cal(5, choices, record)
print(record)
print(f"Answer:{record[-1]}")
这里的核心思想是使用额外的record数组来记录可以找到多少种获取当前数量的方法，例如： record[2] = 2意味着我们可以用来获得2（1+1或2）的总和。
我们有record[target] = sum(record[target-choices[i]])，其中i迭代选择。试着想一想，获得sum=5的方式必须与获得sum=4的方式等有关。
我们假设你的列表由[1,2,5]组成，所以我们有这个递归函数：
f(n,[1,2,5]) = f(n-1,[1,2,5]) + f(n-2,[1,2,5]) + f(n-5,[1,2,5])
因为如果第一个数字总和是1那么你有其余的f(n-1,[1,2,5])选项，如果它是2你有其余的f(n-2,[1,2,5])选项，依此类推......
所以从f(1)开始，用动态编程开始工作。在最坏的情况下，这个解决方案是O(n^2)，当你的列表有O(n)项目时会发生这种情况。
解决方案是这样的：
answers = []
lst = [1,2]
number = 5
def f(target):
val = 0
for i in lst: #O(lst.count())
current = target - i
if current > 0:
val += answers[current-1]
if lst.__contains__(target): #O(lst.count())
val += 1
answers.insert(target,val)
j = 1;
while j<=number: #O(n) for while loop
f(j)
j+=1
print(answers[number-1])
here是一个工作版本。
您希望使用递归遍历每个添加阶段的每种可能性，并在您达到等于预期的数字后传回使用的数字。
def find_addend_combinations(sum_value, addend_choices, base=0, history=None):
if history is None: history = []
if base == sum_value:
return tuple(history)
elif base > sum_value:
return None
else:
results = []
for v in addend_choices:
r = find_addend_combinations(sum_value, addend_choices, base + v,
history + [v])
if isinstance(r, tuple):
results.append(r)
elif isinstance(r, list):
results.extend(r)
return results
你可以把最后一部分写成列表理解，但我认为这种方式更清晰。
与不同顺序的元素的组合被认为是等同的。例如，如果您只是谈论组合，则摘要列表中的＃3和＃5被视为等效。
相反，如果两个集合由不同顺序的相同元素组成，则排列认为这两个集合是唯一的。
要获得您正在寻找的答案，您需要结合这两个概念。
[ins] In [01]: def combination_generator(numbers, k, target):
...: assert k > 0, "Must be a positive number; 'k = {}".format(k)
...: assert len(numbers) > 0, "List of numbers must have at least one element"
...:
...: for candidate in (
...: {'numbers': combination, 'sum': sum(combination)}
...: for num_elements in range(1, k + 1)
...: for combination in itertools.combinations_with_replacement(numbers, num_elements)
...: ):
...: if candidate['sum'] != target:
...: continue
...: for permuted_candidate in itertools.permutations(candidate['numbers']):
...: yield permuted_candidate
...:
[ins] In [02]: {candidate for candidate in combination_generator([1, 2], 5, 5)}
Out[02]:
{(1, 1, 1, 1, 1),
(1, 1, 1, 2),
(1, 1, 2, 1),
(1, 2, 1, 1),
(1, 2, 2),
(2, 1, 1, 1),
(2, 1, 2),
(2, 2, 1)}