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
  • 4,271
  • 8
  • 34
  • 56
huyuxiang
  • 125
  • 6
  • 7
    Can you fix the indentation, please? – timgeb May 24 '20 at 19:39
  • 2
    Simple. Replace k with `self.k` – mad_ May 24 '20 at 19:40
  • @timgeb indentations seems alright – Sabito stands with Ukraine May 24 '20 at 19:40
  • 1
    Because you assign to `k` in the function it becomes a local variable to that function. Then when trying to do `k-1` it is not defined yet (in that function's scope) – Tomerikoo May 24 '20 at 19:43
  • 2
    Does this answer your question? [Python 3: UnboundLocalError: local variable referenced before assignment](https://stackoverflow.com/questions/10851906/python-3-unboundlocalerror-local-variable-referenced-before-assignment) ; https://stackoverflow.com/questions/18002794/local-variable-referenced-before-assignment-in-python ; https://stackoverflow.com/questions/37651721/why-am-i-getting-a-local-variable-referenced-before-assignment-error – Tomerikoo May 24 '20 at 19:43
  • @Tomerikoo, i think OP is aware of the situation with `k`. Their question is `why does res = [] work but not k =0?` – Mustafa Aydın May 24 '20 at 19:46
  • 1
    @MustafaAydın still, the answer is in those links. The simple reason is that assignment will always work. Doing `k = k-1` is also **reading** the value of `k` which is not yet defined – Tomerikoo May 24 '20 at 19:48
  • @Tomerikoo, yes, but by `why does res = [] work`, OP means the further operation of `res.append(..)`, which is not exactly an assignment, is it? (and not exactly reading, either) – Mustafa Aydın May 24 '20 at 19:51
  • 1
    @MustafaAydin, exactly. A call to the `append` method is not an assignment and therefore doesn't cause the compiler to treat `res` as local to `getPermutation`. – Daniel Walker May 24 '20 at 19:54
  • 1
    @DanielWalker You mean `backtrack`. It actually is local to `getPermutation` – Tomerikoo May 24 '20 at 19:56
  • Ah, yes. That's what I meant. – Daniel Walker May 24 '20 at 19:58
  • @Tomerikoo sorry missed that.. – Sabito stands with Ukraine May 24 '20 at 20:05
  • @huyuxiang, did any of the answers below work for you? – Daniel Walker May 29 '20 at 00:41

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
  • 6,380
  • 5
  • 22
  • 45
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_
  • 8,121
  • 2
  • 25
  • 40
-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
  • 798
  • 1
  • 7
  • 15
  • 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