I am working on LeetCode problem 46. Permutations:

Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order.

I thought to solve this using backtracking. My idea is to image this problem as a binary tree and step down a path. When I get to a leaf I pop the visit array and restore to a new root number.

My code below:

   class Solution:
        def permute(self, nums: List[int]) -> List[List[int]]:
            perms = []
            def dfs(curr, l):
                if len(nums) == len(curr):
                    perms.append([int(i) for i in curr])
                    return 
                visit = []
                for t in nums:
                    if str(t) not in curr:
                        visit.append(t)
                        dfs(curr   str(l), t)
                        visit.pop()
                return 
            dfs('', nums[0])
        return perms

I get wrong output for the following test case:

nums = [1,2,3]

The expected output is:

[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

But my code outputs:

[[1,1,2],[1,1,2],[1,1,3],[1,1,3],[1,2,2],[1,2,3],[1,3,2],[1,3,3]]

I don't understand why my output has lists with duplicate ones, even though I check that str(t) not in curr to avoid that duplicate use of a number.

What am I missing?

CodePudding user response：

Here's the backtracking version:

def f(lst, curr = []):
  if len(lst) == len(curr):
    return [tuple(curr)]
  result = []
  for e in lst:
    if e not in curr:
      curr.append(e)
      result.extend(f(lst, curr))
      curr.pop()
  return result

lst = [1, 2, 3, 4]
print(f(lst))

CodePudding user response：

The main reason you have duplicate 1 in your output tuples (in the example) is that in the recursive call you are not appending the right number to curr. l is already in curr once you are in a recursive call! It should be dfs(curr str(t), t) since you have verified that t is not in curr, it should be that number that is appended to it.

And when you make this change, there is no more need for the l parameter in dfs, as l is no longer used.

There are a few other issues however:

• return perms has a wrong indentation (probably a typo in your question?)

• The code assumes that numbers are always single characters when converted to string, but the code challenge indicates that a number may be 10 or may be negative, and so the way you check that a number is already in curr will not be reliable. For instance, if you first visit "10" and then want to visit "1", it will not work because if str(t) not in curr: will not be true.

  Secondly, [int(i) for i in curr] will extract only one-digit numbers, and will fail if you had appended a negative number in curr, as then int('-') will raise an exception.

Not a problem, but the visited list is useless in your code. It is never used to verify anything. And also the return as last statement in dfs is not really needed, as this is the default behaviour.

I would suggest to make curr a list of numbers instead of a string.

Here is your code with the above changes applied:

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        perms = []
        
        def dfs(curr):
            if len(nums) == len(curr):
                perms.append(curr)
                return
                
            for t in nums:
                if t not in curr:
                    dfs(curr   [t])

        dfs([])
        return perms

It would be nice to use a generator here:

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        def dfs(curr):
            if len(nums) == len(curr):
                yield curr
                return
                
            for t in nums:
                if t not in curr:
                    yield from dfs(curr   [t])

        return list(dfs([]))

Finally, there is of course ... itertools:

import itertools

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        return list(itertools.permutations(nums))