python - Python所有具有精确摘要的整数列表列表

Question

我需要一个算法的帮助，该算法采用整数和值的列表并找到所有加起来为值的列表。例如：fn ([1,1,2,2,3],4) -> [[1,1,2],[1,3],[2,2]]

它必须是一个没有添加库的递归解决方案。我花了很多时间来解决这个问题，但到目前为止我什么都没有。

感谢任何帮助，谢谢

Answer 1

我需要有 50 声望才能在上面发表评论，所以在这里发帖。
请不要将此视为答案。

生成该列表的所有可能组合并检查这些组合中的哪些加起来等于目标值。正如上面塞尔丘克所说...

要生成列表的所有可能组合 -

from itertools import combinations 
def mySubset(arr, r): 
    return list(combinations(arr, r)) 
if __name__ == "__main__": 
    arr = [1, 2, 3, 4] 
    r = 3
for x in arr:
  print(mySubset(arr, x))

它给出了以下结果-

[(1,), (2,), (3,), (4,)]                                                                                                               
[(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)]                                                                                       
[(1, 2, 3), (1, 2, 4), (1, 3, 4), (2, 3, 4)]                                                                                           
[(1, 2, 3, 4)]