0

This code gives an error: 'UnboundLocalError: local variable 'k' referenced before assignment'. I understand it's because the outer function doesn't pass the parameter, but why does res = [] works but not k =0?

class Solution:
    def getPermutation(self, n: int, k: int) -> str:
    res = []
    k = 0

    def backtrack(nums, path):
        if not nums:
            k = k - 1
            if k == 0:
                res.append(path)
            return
        if k < 0: return
        for i in range(0, len(nums)):
            backtrack(nums[:i] + nums[i + 1:], path + [nums[i]])

    backtrack(list(range(1, n + 1)), [])
    return res
print(Solution().getPermutation(3, 1))
Sabito 錆兎 stands with Ukraine
  • 3,250
  • 7
  • 26
  • 49
huyuxiang
  • 55
  • 4

3 Answers3

0

The problem is in your backtrack function. The syntax parser sees that you're assigning k to a new value in that first if block. Therefore, the parser has decided that k is local to the backtrack function, even if that if block is not run.

So, suppose you call backtrack when nums is truthy. The local variable k has not been defined and yet you try to compare it with 0.

You need to tell the parser that k refers to the k defined in the higher scope (i.e., getPermutation). You can do this by putting the line

nonlocal k

as the first line of the backtrack function.

The reason you don't have a problem with res is it's never assigned to a new value in backtrack and so the parser has no reason to assume that it's a local variable.

Daniel Walker
  • 5,220
  • 3
  • 18
  • 39
0

Make use of Object oriented programming. Replace k with self.k which can be used throughout with the object instance. Python questions about the initialization of k because in one of the if condition you are initializing the k variable which becomes a local variable and Python suspects that k might not have initialized before using it. Simple solution is to use self.k. In that case k becomes the property of an instance.

class Solution:
    def getPermutation(self, n: int, k: int) -> str:
        res = []
        self.k = 0

        def backtrack(nums, path):
            if not nums:
                self.k = k - 1
                if self.k == 0:
                    res.append(path)
                return
            if self.k < 0: return
            for i in range(0, len(nums)):
                backtrack(nums[:i] + nums[i + 1:], path + [nums[i]])

        backtrack(list(range(1, n + 1)), [])
        return res
print(Solution().getPermutation(3, 1))
mad_
  • 7,844
  • 2
  • 22
  • 37
-1

You declared both k and res inside of getPermutation method, and they are not visible outside of it.

You should create variable inside init method:

def __init__(self):
    self.res = []
    self.k = 0

Therefore when you create instance of the Solution class, it would have its own k and res which you can access as self.k/self.res.

nenadp
  • 601
  • 1
  • 5
  • 13
  • I think you mean "instance variables" and not "class variables". Also, doesn't it seem like a waste of memory (not that we're talking about much here but still) to permanently hold on to `k` and `res` even after `getPermutation` returns? – Daniel Walker May 24 '20 at 19:53
  • You are right, I got confused because of the indentation, somehow missed getPermutations(). Since he calls backtrack recursively, I don't see the other way than that, since values would be overwriten whenever backtrack is executed. He could also pass them as parameters, with the default values set to 0 and []. – nenadp May 24 '20 at 20:01
  • I just ran a simple test case (slightly too long to post in this comment) and the `nonlocal` keyword takes care of any issues coming from recursion. – Daniel Walker May 24 '20 at 20:05
  • You got the point about the memory, but I personally would favor instance variable over nonlocal. He could potentially have tens of methods and declare k somewhere else, it's pretty common variable name. I would gladly waste couple of bytes in favor of code simplicity. – nenadp May 24 '20 at 20:15
  • But the tens of methods wouldn't be sharing the same `k`. – Daniel Walker May 24 '20 at 20:16