如何找到组中所有可能的子组

Question

假设我们有组1、2、3，因此可能的子组是：

    {1,2,3}
    {1} {2,3}
    {1,2} {3}
    {1,3} {2}
    {1} {2} {3}

你明白了。在

我必须用递归来做。到目前为止我所拥有的（不起作用），而且有点不同。 这个想法是你有一个代表立方体的整数的列表（用来建造一座塔），并且你想要建造尽可能多的具有一定高度的塔。假设你得到了 立方体[5,2,6,6,1,1,4]，你想要的高度是7，那么最好的构建是[5,2] [6,1] [6,1] [4]。在

代码：

^{pr2}$

但我只得到[5,2] [6,1]。有什么想法吗？在

Answer 1

你的主要问题是你没有重复你没有使用的值，例如： 先拿5，2 比6,6，但不好，所以你跳过，然后取6,1 但你再也不会拿前6个了，再得到一个6，1的连击。 这就是为什么你必须重复所有的值后，你选择一个组合。在

代码（可能更好，用你的逻辑）：

    def find_tower(blocks, height):

def solve(groups, cur_group, index):
    if sum(cur_group) == height:
        new_group = list(groups)# if tower is on right height
        new_group.append(cur_group)# add to groups of towers
        return solve(new_group, [], 0)
    if index == len(blocks):# if index max
        return groups
    elif sum(cur_group) > height:# if its higher than height
        return groups
    elif blocks[index] is None:# if its a None index skip
        return solve(groups, cur_group, index+1)

    temp = blocks[index]
    blocks[index] = None# changing used value to none
    r1 = solve(groups, cur_group + [temp], index+1)
    blocks[index] = temp# puttin back used value
    r2 = solve(groups, cur_group, index+1)
    return max(r1, r2, key=lambda x: len(x))# return longer group
return solve([], [], 0)