python - 如何从子集列表中过滤出唯一的组合

Question

我试图想出一个脚本来实现 Subset sum Prob ，在 this post 第一个脚本的帮助下。所以，现在运行我的脚本，我得到这个:

maci:python sant$ ./subsetSum.py -n3,4,5,6,7,8,9,3,4,5 -t12
[3, 4, 5] => 12
[3, 4, 5] => 12
[3, 5, 4] => 12
[3, 6, 3] => 12
[3, 9] => 12
[3, 4, 5] => 12
[4, 5, 3] => 12
[4, 8] => 12
[4, 3, 5] => 12
[5, 7] => 12
[5, 3, 4] => 12
[7, 5] => 12
[8, 4] => 12
[9, 3] => 12
[3, 4, 5] => 12

效果很好。但如何仅过滤掉唯一的子集呢？结果中，1、2、15 完全相同，还有 6 个，是[3,4,5]的组合。如何只打印一份而不是全部？干杯!!

PS。我知道 Q 可能没有反射(reflect)我真正想要的，所以请随意改进它。

Answer 1

不必在列表中多次添加数字，只需添加(数字，多重性)的元组所以你的输入将变成 [(3, 2), (4, 2), (5, 2), (6, 1), (7, 1), (8, 1), (9, 1) ]。

这样可以轻松创建没有重复的子集。你可以这样做:

for i in n[1]:
    subset_sum_recursive(remaining, target, partial + i * [n[0]])

或者，不仅保留“部分”列表，还保留“废弃”列表可能会更容易。然后你可以检查

if(n not in discarded)
    subset_sum_recursive(remaining,target,partial + [n])