1

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?

Improve this question
8
  • Can you draw a tree you want to traverse? Commented Jan 27, 2023 at 4:53
  • @n.m. yes but not sure how to share. I can create a tree for each permutarion with first integer as the root and las as a leaf example 1 as root then 2 then 3 with edges in between then another three with 2 as root and say 3 as left represents 213 permutation Commented Jan 27, 2023 at 5:15
  • In the question you are implying that the problem is a tree and each leaf is a solution. I don't see that in your comment. You can upload an image to any free image hosting, edit the question and add a link or possibly an inline image. Commented Jan 27, 2023 at 5:25
  • The central, underlying problem is that recursively calling dfs(curr + str(l), t) has no effect on the local visit, because each call to a function (including recursive calls, which are not in any way special) has its own local variables, and visit is local. Please see the linked duplicate for details (the problem described is slightly different, but the cause and solution are the same). There are several other typos and other such minor issues in the code; but we do not provide a debugging service; questions are supposed to be about one problem. Commented Jan 27, 2023 at 8:16
  • @KarlKnechtel, I think the dupe reference is wrong. The asker is not expecting the recursive call to return anything: the None is intended. They rely on the side effect of populating perms, and so the return value of the recursive function is not relevant here. Also the visit list you refer to is irrelevant. The code doesn't rely on it, so it has no positive nor negative effect on the algorithm, which relies on curr for the "visited" behaviour. Commented Jan 27, 2023 at 9:38

2 Answers 2

Reset to default
0

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))
Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

-1

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))
Improve this answer

7 Comments

This talks about some aspects of the question but does not seem to provide a backtracking solution. (Did not downvote.)
According to Wikipedia a backtracking solution is one "that incrementally builds candidates to the solutions, and abandons a candidate ("backtracks") as soon as it determines that the candidate cannot possibly be completed to a valid solution". The candidates are represented by curr, and it is abandoned when the condition of the if statement is not true. The definition of "backtracking" is quite broad and can be interpreted differently. Maybe you have an issue with the fact that curr is dealt with as immutable and the "incrementing" consists of creating a new copy?
Neither yours or my solution seem to fit this definition since rather than determining "that the candidate cannot possibly be completed to a valid solution," they quite literally explore a candidate to its completion, then add it to a list. You make a good point and it could be that the kind of backtracking where the mutable list is altered in a "winding back" fashion is a more colloquial understanding of the term, "backtracking."
Well, we can say that the detection of "cannot possibly be completed" occurs at the if statement which rejects duplicate entries even before adding them. As there are no other constraints in this particular problem, no other cases need to be rejected. But I think we are diving too deep here, as many use the term backtracking in a very loose way, more as a synonym for recursion, and it wouldn't surprise me this is the case in this question too.
Let's ask the OP!
|

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.