def permute(self, nums: List[int]) -> List[List[int]]:
res = []
perm = []
def dfs(i):
if len(nums) == 0:
res.append(perm[:])
return
for j in range(len(nums)):
perm.append(nums[j])
n = nums.pop(j)
dfs(i+1)
perm.pop()
nums.insert(j,n)
dfs(0)
return res
This function gives the correct result for some reason even though it shouldn't as nums[j] should be out of bounds. Can someone explain why this works?
To get an index out of bounds error, you would have to call nums[j], with j >= len(nums). Here's why that never happens in your code.
You use j to identify a location within nums three times:
for loop, you call nums[j] to append to perm. So long as j is a value between 0 and len(nums)-1 (because range(n) = (0, 1, 2, ..., n-2, n-1)), then you can't be out of range. The only way you'd end up being out of range is if the next time you called nums[j], the length of nums had changed. Let's see if that happens.index out of bounds error is on the next line - n = nums.pop(j). Well there can be no problem here - you were able to grab the value of nums at j on the previous line, so why shouldn't you be able to pop that value out of nums now? But now you've mutated nums, and if you call nums[j] again, AND if j is greater than len(nums) - 2, you'd be in trouble - let's see if that happens.dfs(i+1), which opens up a new invocation of dfs, and an entirely new for loop, with a new j, that restarts at 0, and a new nums that's one shorter than it was in the previous function call. If nums is empty, you never enter the for loop, and if nums isn't empty, you enter the for loop with j = 0 - so no risk of being out of bounds here.for loop with j = 0 and with nums truncated by one, until you get to the bottom of the recursion hole and nums == 0. At this point, you climb back up out of the recursion hole and carry on where you left off - after the last dfs(i+1) call. When you jumped into the recursion hole, you'd just mutated nums, and were in imminent danger of an index out of bounds error...perm.pop()) kinda doesn't count in the nums/j saga we're on - so we'll skip past it.nums.insert(j, n). nums.insert(j, n) places the value assigned to n at the index assigned to j - 1. e.g: taking a list lst with 4 items in it, calling lst.insert(4, <val>) would take <val> and place it at the end of nums - making your nums.insert(j, n) equivalent to saying nums.append(n). From the time you popped n out of nums, to now, you've basically just shuffled it from where it was to the end of nums. You WERE sailing perilously close to an index out of bounds error, but you've now undone the mutation you had previously inflicted on nums, so as you exit the for loop, nums is exactly as long as it was when you entered it. Going back to the start of the for loop and incrementing j before reentering the for loop poses no risk to you of an index out of bounds error.