尝试使用递归方法生成字符串的子集

Question

尝试在python中使用递归实现算法。似乎缺少一些我无法调试的东西。

我的方法是具有两个递归分支，并在每次递归时传递一个元素。详细信息如下：

## input pattern : "ab"
## output pattern : ["", "a", "b", "ab"]

递归树将类似于此模式

#           "ab" [ROOT]
#                   |
#           -a           +a
#           |             |
#       -b      +b    -b    +b
# =>    ""      "b"     "a"     "ab"

我现有的代码如下：无法正常工作。

def gen_subset(slist):
    def helper(slist,i,temp,out):
        if len(slist) == i:
            out.append(temp)
            return()
        else:
            helper(slist,i+1,temp,out)
            temp.append(slist[i])
            helper(slist,i+1,temp,out)

    out = []
    helper(slist,0,[],out)
    return out

s = "ab"
print (gen_subset([c for c in s]))

此代码产生错误的结果。

输出量

[['b', 'a', 'b'], ['b', 'a', 'b'], ['b', 'a', 'b'], ['b', 'a', 'b']]

我在这里想念什么吗？

Answer 1

更改temp.append(slist[i])为temp = temp + [slist[i]]。

发生这种情况是因为就地temp.append()修改了temp变量。
相反，我们需要将的副本传递temp给下一个递归调用。