I'm attempting to create permutations from an input list. My recursion fails and only brings me back a single list, where there should be multiple. I'm uncertain as to whats wrong with my logic - new to recursion.
class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
answer, perm = [], []
self.dfs(nums, answer, perm)
return answer
def dfs(self, nums, answer, perm):
if not nums:
answer.append(perm)
for ind, ele in enumerate(nums):
perm.append(ele)
nums.pop(ind)
self.dfs(nums,answer, perm)
Expected: [[1,2,3],[2,1,3],[2,3,1],[1,3,2],[3,1,2],[3,2,1]] Actual: [[1,2,3]]
It can be helpful to log out some of the data passing through your solution so you can see exactly what you are doing wrong. If we log nums and perm at each step of your code, we get the following:
[1, 2, 3] # nums 0
[] # perm 0
[2, 3] # nums 1
[1] # perm 1
[3] # nums 2
[1, 2] # perm 2
[] # nums 3
[[1, 2, 3]] # result
All your code currently does it move elements from a list to a sublist containing the original list. You need to keep track of which elements have been added to the sublist without emptying the original list, and then you can create your desired permutations. You can still accomplish this with recursion, but adding the functionality of the set will make your life a lot easier.
Here is a basic example, which you can adapt as needed:
def dfs(data, perm_out=None):
if not perm_out:
perm_out = []
if not data:
return [perm_out]
res = []
for point in data:
u = {point}
diff = data - u
res += dfs(diff, perm_out + [point])
return res
Calling it on your simple input data:
i = [1, 2, 3]
u = dfs(set(i))
print(u)
[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]