python - 打印n选择使用递归的k组合算法

这一定是一个典型的面试问题，然而，我有一个问题理解它。
下面是我在Python中的实现，如果运行它，它只打印ab, ac, ad它不会进入'b' (bc, bd)级别。

def Print_nCk (the_list, k, str_builder, used):
    if len(str_builder) == k:
        print str_builder
        return
    else:
        for i in xrange(len(the_list)):
            if used[i] !=True:
                str_builder+=the_list[i]
                used[i] = True
                Print_nCk(the_list, k, str_builder, used)
                str_builder = str_builder[:-1]


Print_nCk(['a','b','c','d'], 2, "",[False,False,False,False])

正确的答案是当超过上述行时ab,ac,ad,bc,bd,cd。
我知道在这里不使用usedparam（http://www.geeksforgeeks.org/print-all-possible-combinations-of-r-elements-in-a-given-array-of-size-n/）的正确实现，但是
我的问题是我的实现有什么问题？
你能弄清楚吗？
为了调试，我每次都打印出“used”。used参数在打印“ad”后变为（true，true，true，true），则不会变深。如果我坚持使用used，那么修复used的聪明方法是什么？

最佳答案

当您返回时，忘记设置used[i]：

def Print_nCk (the_list, k, str_builder, used):
    if len(str_builder) == k:
        print str_builder
        return
    else:
        for i in xrange(len(the_list)):
            if used[i] != True:
                str_builder += the_list[i]
                used[i] = True
                Print_nCk(the_list, k, str_builder, used)
                str_builder = str_builder[:-1]
                used[i] = False


Print_nCk(['a','b','c','d'], 2, "",[False,False,False,False])

在当前实现中，从选择used[i]作为值时起，就将True设置为i。但是，如果以后决定选择另一个分支，则应正确记账，从而取消设置used[i]。
注意，现在将生成"ab"和"ba"。因此，生成具有对称性的组合如果不需要，可以使用其他参数。以确保使用的索引不低于先前选择的索引：

def Print_nCk (the_list, k, str_builder, used, prev = 0):
    if len(str_builder) == k:
        print str_builder
        return
    else:
        for i in xrange(prev,len(the_list)):
            if used[i] != True:
                str_builder += the_list[i]
                used[i] = True
                Print_nCk(the_list, k, str_builder, used, i+1)
                str_builder = str_builder[:-1]
                used[i] = False


Print_nCk(['a','b','c','d'], 2, "",[False,False,False,False])

然而，这或多或少地违背了使用“used”数组的目的您只需使用prev：

def Print_nCk (the_list, k, str_builder, prev = 0):
    if len(str_builder) == k:
        print str_builder
        return
    else:
        for i in xrange(prev,len(the_list)):
            str_builder += the_list[i]
            Print_nCk(the_list, k, str_builder, i+1)
            str_builder = str_builder[:-1]


Print_nCk(['a','b','c','d'], 2, "")

然后打印：

>>> Print_nCk(['a','b','c','d'], 2, "")
ab
ac
ad
bc
bd
cd

关于python - 打印n选择使用递归的k组合算法，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/44914234/