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

Question

Given two numbers n and k and you have to find all possible combination of k numbers from 1…n. I am implementing this using DFS algorithm. But my ans array return None, whereas if I try to print temp the combinations are generated correctly. What am I doing wrong ? In this link from Geeks for Geeks It is working correctly for C++

Here is my code:

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

Expected work:

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

Answer 1

You are modifying the temp list which is passed as a reference. You should pass a copy of temp in recursion, e.g.:

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

Answer 2

You need to append a copy of the relevant data, not the mutable list itself like:

Append a copy

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

Test Code:

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

Results:

1 2 
1 3 
1 4 
2 3 
2 4 
3 4