无法使用递归在python列表中生成数字组合

Question

我试图使用递归在python列表中生成数字的组合 我的代码如下

nums = [2,3,4,6]

def backtrck(temp, starting_index, nums):
    if len(temp) == 2:
        print(temp)
        return
    temp.append(nums[starting_index])
    for i in range(starting_index + 1, len(nums)):
        backtrck(temp, i, nums)

backtrck([], 0, nums)

由于某些原因，上述代码无法生成正确的组合

代码目标：我想生成所有以索引0开始的数字组合，其长度应等于2

预期产出

[2, 3]
[2, 4]
[2, 6]

实际产出

[2, 3]
[2, 3]
[2, 3]
[2, 3]

我不明白这个递归出了什么问题，我希望有人能帮我解决这个问题

Answer 1

对于递归，我的建议是保持简单，让递归为您完成工作：

def backtrck(numbers):
    if len(numbers) < 2:
        return []

    first, second, *rest = numbers

    return [[first, second]] + backtrck([first] + rest)

nums = [2, 3, 4, 6]

print(*backtrck(nums), sep='\n')

输出

> python3 test.py
[2, 3]
[2, 4]
[2, 6]
>

Answer 2

您的功能有什么问题：

在两次递归调用之后temp变为[2,3]，然后在下一次递归中满足基本情况（len(temp) == 2:），并且该函数实例返回而不添加任何内容。下一个for循环迭代递归，同样的事情也会发生。一旦temp成为[2,3]，它就永远不会改变

如何修复它：

函数的结构存在许多问题，它不是一个简单的单行修复。你需要想办法

• 当满足基本情况时
  • 捕获（或打印）temp
  • 向上一个函数返回有意义的内容，以便继续进行组合
• 函数需要根据递归调用的返回值进行操作
• 将for循环添加到递归过程/流程会使事情变得复杂，可能会想办法不使用它

我将从函数开始。我不知道你是否要求别人给你一个全新的函数，所以我将搜索有关递归解决方案的问题，以查找/生成列表项组合

---

以下是一些相关的SO问题/答案。如果其中任何一个解决了您的问题，请告诉我们，以便我们可以将您的标记为副本。大多数没有taken two-at-a-time约束，但也许您可以进行调整。还有很多

Recursive function that returns combinations of size n chosen from list
Recursively find all combinations of list
python recursion list combinations without using generator
Using recursion to create a list combination

松散相关：
Nth Combination
Finding all possible combinations of numbers to reach a given sum
Creating all possible k combinations of n items in C++-不是Python，但算法可能有用

Answer 3

当您可以简单地使用for循环时，递归是不必要的：

nums = [2,3,4,6]

def backtrck(starting_index, nums):
    start = nums[starting_index]
    for num in nums[starting_index + 1:]:
        print([start, num])
        
backtrck(0, nums)

输出：

[2, 3]
[2, 4]
[2, 6]

其中，切片nums[start_index + 1:]返回nums列表中所有元素的列表，从starting_index后面的一个标记开始

更新

既然您已经指出递归在代码中是必要的，只需将backtrck(temp, i, nums)递归调用替换为backtrck(i, nums, [temp[0], nums[i]])即可保留列表的起始索引：

nums = [2, 3, 4, 6]

def backtrck(starting_index, nums, temp=[]):
    if len(temp) == 2:
        print(temp)
        return
    temp.append(nums[starting_index])
    for i in range(starting_index + 1, len(nums)):
        backtrck(i, nums, [temp[0], nums[i]])

backtrck(0, nums)

输出：

[2, 3]
[2, 4]
[2, 6]

请注意，我已将位置参数temp更改为关键字参数。它仍然可以使用temp作为位置参数，但是如果temp列表总是以空开头，那么它就不那么实用了