Permutations

Intuition

• You need to visualize the number that is dequeued as spinning back to the front
• Additionally, note that by appending the element to the back, you are simply handling the fact that you are doing “for i in range(len(cur))”, in which you have to do that or otherwise you would go out of bounds.
  • ex) If you have [1, 2], and then you pop and append afterwards, you get [2, 1] and then when you pass the element into your next recursion, you pop off the 2 and get [1], so all that the code does is flip the elements, wherein if you had [1, 2] before, you have [2, 1] when returned.
• Also, only worry about 2 levels of your tree (the last 2). If you can understand 1-2 levels of a recursion, then you understand the full recursion.

Runtime

$O(NN!)$ since for each of the $N!$ permutations, you need $O(N)$ work to copy the current array into the res array.

Code

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        def r(cur):
            res = []
            if len(cur) == 1:
                return [[cur[0]]]
            
            for _ in range(len(cur)):
                popped = cur.popleft()
                permutations = r(cur)
                for perm in permutations:
                    perm.append(popped)   
                
                res.extend(permutations)
                cur.append(popped)
 
            return res
 
        return r(deque(nums))

Notes

---

References

https://leetcode.com/problems/permutations/