首先，我将使用含义很深的变量名，以便使代码易于理解。然后，在我理解了这个问题之后，这显然是一个递归问题，因为一旦您选择了一个数字，寻找其余平方的可能值的问题就完全一样，只是其中的值不同。
所以我会这样：
from __future__ import divisionfrom math import ceildef make_combos(max_val,target_sum,n_cells): combos = [] # The highest possible value of the next cell is whatever is # largest of the max_val, or the target_sum minus the number # of remaining cells (as you can't enter 0). highest = min(max_val, target_sum - n_cells + 1) # The lowest is the lowest number you can have that will add upp to # target_sum if you multiply it with n_cells. lowest = int(ceil(target_sum/n_cells)) for x in range(highest, lowest-1, -1): if n_cells == 1: # This is the last cell, no more recursion. combos.append((x,)) break # Recurse to get the next cell: # Set the max to x (or we'll get duplicates like # (6,3,2,1) and (6,2,3,1), which is pointless. # Reduce the target_sum with x to keep the sum correct. # Reduce the number of cells with 1. for combo in make_combos(x, target_sum-x, n_cells-1): combos.append((x,)+combo) return combosif __name__ == '__main__': import pprint # And by using pprint the output gets easier to read pprint.pprint(make_combos( 6,12,4))
我还注意到您的解决方案似乎仍然有问题。例如，对于这些值，
max_val=8, target_sum=20 andn_cells=5您的代码找不到解决方案
(8,6,4,1,1,)。我不确定这是否意味着我错过了一条规则，但是据我了解，这些规则应该是有效的选择。
这是一个使用生成器的版本，如果值真的很大，它会节省几行代码和内存，但是作为递归，生成器“获取”可能很棘手。
from __future__ import divisionfrom math import ceildef make_combos(max_val,target_sum,n_cells): highest = min(max_val, target_sum - n_cells + 1) lowest = int(ceil(target_sum/n_cells)) for x in xrange(highest, lowest-1, -1): if n_cells == 1: yield (x,) break for combo in make_combos(x, target_sum-x, n_cells-1): yield (x,)+comboif __name__ == '__main__': import pprint pprint.pprint(list(make_combos( 6,12,4)))
