这是我自己的使用动态编程的Python解决方案。这里给出算法。
def get_subset(lst, s): '''Given a list of integer `lst` and an integer s, returns a subset of lst that sums to s, as well as lst minus that subset ''' q = {} for i in range(len(lst)): for j in range(1, s+1): if lst[i] == j: q[(i, j)] = (True, [j]) elif i >= 1 and q[(i-1, j)][0]: q[(i, j)] = (True, q[(i-1, j)][1]) elif i >= 1 and j >= lst[i] and q[(i-1, j-lst[i])][0]: q[(i, j)] = (True, q[(i-1, j-lst[i])][1] + [lst[i]]) else: q[(i, j)] = (False, []) if q[(i, s)][0]: for k in q[(i, s)][1]: lst.remove(k) return q[(i, s)][1], lst return None, lstdef get_n_subset(n, lst, s): ''' Returns n subsets of lst, each of which sums to s''' solutions = [] for i in range(n): sol, lst = get_subset(lst, s) solutions.append(sol) return solutions, lst# print(get_n_subset(7, [1, 2, 3, 4, 5, 7, 8, 4, 1, 2, 3, 1, 1, 1, 2], 5))# [stdout]: ([[2, 3], [1, 4], [5], [4, 1], [2, 3], [1, 1, 1, 2], None], [7, 8])
