生成所有可能的Kakuro解决方案的字典

Question

我刚开始学习Python，有一个想法，试图为Kakuro谜题生成一个包含所有可能解决方案的字典。有一些关于这些谜题的帖子，但没有一篇展示如何生成上述词典。我想要的是一个字典，它有3-45的键，它们的值是整数的元组，这些整数和键相加(例如mydict[6]=([1,5]，[2,4]，[1,2,3]((。它本质上是一个子集和问题——https://mathworld.wolfram.com/SubsetSumProblem.html

我自己也尝试过，它适用于三位数长的元组。我的方法要求元组中每个额外的整数都有一个循环，因此需要我编写一些非常重复的代码！有更好的方法吗？我觉得我想循环创建循环，如果这是一件事的话？

def kakuro():
L = [i for i in range(1,10)]
mydict = {}
for i in L:
L1 = L[i:]
for j in L1:
if i+j in mydict:
mydict[i+j].append((i,j))
else:
mydict[i+j] = [(i,j)]
L2 = L[j:]
for k in L2:
if i+j+k in mydict:
mydict[i+j+k].append((i,j,k))
else:
mydict[i+j+k] = [(i,j,k)]
for i in sorted (mydict.keys()):
print(i,mydict[i])
return

我的第二轮尝试-越来越好！

def kakurodict():
from itertools import combinations as combs 
L = [i for i in range(1,10)]
mydict={}
mydict2={}
for i in L[1:]:
mydict[i] = list(combs(L,i))
for j in combs(L,i):
val = sum(j)
if val in mydict2:
mydict2[val].append(j)
else:
mydict2[val] = [j]    
return mydict2

Answer 1

所以这是用以下假设编写的。

• dict[n]不能具有值为[n]的列表
• 子集中的每个元素都必须是唯一的

我希望其他人能提供更好的解决方案，因为当我们为值3-45生成所有子集时，需要相当长的时间。我相信子集和生成问题的时间复杂度是2^n，所以如果n是45，这是不理想的。

import itertools
def subsetsums(max):
if (max < 45):
numbers = [x for x in range(1, max)]
else:
numbers = [x for x in range(1, 45)]
result = [list(seq) for i in range(len(numbers), 0, -1) for seq in itertools.combinations(numbers, i) if sum(seq) == max]
return(result)
mydict = {}
for i in range(3, 46):
mydict[i] = subsetsums(i)
print(mydict)