I have a solution to the following problem: https://leetcode.com/problems/combinations/
List[List[int]]:
def backtrack(first = 1, curr = []):
# if the combination is done
if len(curr) == k:
output.append(curr[:])
for i in range(first, n + 1):
# add i into the current combination
curr.append(i)
# use next integers to complete the combination
backtrack(i + 1, curr)
# backtrack
curr.pop()
output = []
backtrack()
return output
My question is around curr.pop() why are we popping the curr combination each iteration? Shouldn't there be some condition like if curr is already in output?
Another question is for the recursion call backtrack(i+1, curr) - when this is called, am I right in saying that 'i+1' takes the place of 'first' in the main function?
The (copy of) the combination curr is output at the deepest level of recursion (well, it should be the deepest, currently the code continues looping even when it is known in advance to be futile i.e. to have no chance of producing any output, i.e. when the length of curr is greater than k).
The combination is built on the way in, one element at a time.
The element is added, the recursion is entered (and eventually the deepest level is reached and the copy of the combination is collected into the output) and then recursion unwinds, eventually getting out of that recursive call --- so we must remove the element which we've put in, so we can put the next element into the curr, on the next iteration of that for ... range ... loop (which should be guarded by if len(curr) < k: ....).
So yes, i+1 is the "new" value of first -- in the next for ... range ... loop, one level deeper. Thus what's happening here is that the recursion in effect builds the nested loops structure where the deepest loop has the curr fully set and populated, and so adds it to the output.
Or in pseudocode:
for i1 in range( 1, n+1):
for i2 in range( i1+1, n+1):
.........
for ik in range( ik1+1, n+1):
output.append( [i1,i2,...,ik1,ik] )
(except for the inefficiency in your code where it keeps creating more loops for k+1, k+2, ..., n levels potentially, even when we already know that it's all for naught as we only ever need the combinations of length k).
This is the gist of it, though your code does not build the curr while at the deepest level, as shown above, but rather by appending ij at each (jth) level. That's why it needs to pop it before appending the next value from the for loop, in effect updating the jth position in curr:
for i1 in range( 1, n+1):
curr.append(i1)
for i2 in range( i1+1, n+1):
curr.append(i2)
.........
for ik in range( ik1+1, n+1):
curr.append(ik)
output.append( curr )
curr.pop()
.........
curr.pop()
curr.pop()
The same effect could be achieved by changing the jth value in curr directly. You'd need to create the k-long curr upfront for that (filled with some non-important values initially), and introduce an additional counter for that:
for i1 in range( 1, n+1):
curr[0] = i1 # j == 0
for i2 in range( i1+1, n+1):
curr[1] = i2 # j == 1
.........
for ik in range( ik1+1, n+1):
curr[k-1] = ik # j == k-1
output.append( curr )
And that's what (chronological) backtracking is all about. Just nested loops, each loops maintaining its state, ready to try another alternative when the control returns (backtracks) to it.
Also, that's what "monads" are all about. Just generalized nested loops, working in tandem to produce the output from inside the deepest one, no matter how many levels there are above it.