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

Question

这一定是一个经典的面试问题，但是，我在理解它时遇到了问题。

下面是我在 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当上面的线通过时。

我知道从这里不使用used参数的正确实现（http://www.geeksforgeeks.org/print-all-possible-combinations-of-r-elements-in-a-given-array-of-size-n/）但我的问题是我的实现有什么问题？

你能解释一下吗？

为了调试，我每次都打印出“used”。该usedPARAM打印“广告”，那么它不走比更深之后变为（不错，不错，不错，不错）。used如果我坚持使用，修复 的聪明方法是used什么？

Answer 1

回溯时忘记取消设置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].

注意 now"ab"和"ba"will 会生成。因此，您可以生成具有对称性的组合。如果您不想这样，可以使用附加参数。这可确保您不使用低于先前选择的索引：

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])

然而，这或多或少违背了使用“使用过的”数组的目的。您可以简单地使用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