Составьте все комбинации размера k, начиная с 1 до n.

Question

Даны два числа n и k, и вы должны найти все возможные комбинации чисел k из 1 ... n. Я реализую это с помощью алгоритма DFS. Но мой массив ans возвращает None, тогда как если я пытаюсь напечатать temp, комбинации генерируются правильно. Что я делаю неправильно ? По этой ссылке от Geeks for Geeks Работает правильно для 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

Вам необходимо добавить копию соответствующих данных, а не сам изменяемый список, например:

Добавить копию

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 2 
1 3 
1 4 
2 3 
2 4 
3 4 

Answer 2

Вы изменяете список temp, который передается в качестве ссылки. Вы должны передать копию temp в рекурсии, например:

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