从 1 到数字 n 进行大小 k 的所有组合

Question

给定两个数字 n 和 k，你必须从 1…n 中找到 k 个数字的所有可能组合。我正在使用 DFS 算法实现这个。但是我的 ans 数组 return None，而如果我尝试打印 temp，则组合会正确生成。我究竟做错了什么？在这个来自 Geeks for Geeks 的 link 中它对 C++

工作正常

这是我的代码：

def DFSUtil(ans, temp, n, left, k):
    if k == 0:
        ans.append(temp)
        return

    for i in range(left, n+1):
        temp.append(i)
        DFSUtil(ans, temp, n, i+1, k-1)
        temp.pop()


def DFS(n, k):
    ans = []
    temp = []
    DFSUtil(ans, temp, n, 1, k)
    return ans

n = 5
k = 3
ans = DFS(n, k)
for i in range(len(ans)):
    for j in range(len(ans[i])):
        print(ans[i][j], end=' ')
    print()

预期工作：

Input : n = 4 
        k = 2
Output : 1 2 
         1 3 
         1 4 
         2 3 
         2 4 
         3 4

Answer 1

您正在修改作为参考传递的 temp 列表。您应该递归传递 temp 的副本，例如：

DFSUtil(ans, temp.copy(), n, i+1, k-1)

Answer 2

您需要附加相关数据的副本，而不是可变列表本身，例如：

追加副本

if not(ans and ans[-1] == temp[:-1]):
    ans.append(list(temp[:-1]))

测试代码：

def DFSUtil(ans, temp, n, left, k):
    if k == 0:
        if not(ans and ans[-1] == temp[:-1]):
            ans.append(list(temp[:-1]))
        return

    for i in range(left, n + 1):
        temp.append(i)
        DFSUtil(ans, temp, n, i + 1, k - 1)
        temp.pop()


def DFS(n, k):
    ans = []
    temp = []
    DFSUtil(ans, temp, n, 1, k)
    return ans


n = 5
k = 3
ans = DFS(n, k)
for i in range(len(ans)):
    for j in range(len(ans[i])):
        print(ans[i][j], end=' ')
    print()

结果：

从 1 到数字 n 进行大小 k 的所有组合

Make all combinations of size k starting from 1 to number n

python

microsoft-distributed-file-system

python-3.x

追加副本

测试代码：

结果：