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