def combination(n,k):
combi=[]
def backtrack(start,comb):
print(comb)
if len(comb)==k:
combi.append(comb.copy())
return
for i in range(start,n+1):
# print(i)
cur=[i]
backtrack(i+1,comb+cur)
comb.pop()
print("comb after",comb)
backtrack(1,[])
return combi
combination(4,3)
I am getting IndexError: pop from empty list.
When I printed comb to identify error, I am getting this:
1
[]
i is 1
2
[1]
i is 2
3
[1, 2]
i is 3
4
[1, 2, 3]
comb after [1]
i is 4
5
[1, 4]
comb after []
comb after []
i is 3
4
[3]
i is 4
5
[3, 4]
comb after []
Why is my code popping 2 and 3 both when it should only pop 3 after getting [1,2,3].why isnt it popping only 3. What am I doing wrong?
data_geek is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
1
comb is indeed empty. You never appended anything to it.
The misunderstanding probably comes from the argument you build for the recursive call:
backtrack(i+1,comb+cur)
…but that doesn’t modify comb. That just creates a new list that has one more element, and which in the recursive execution of the function is assigned to a local name that happens also be comb. But that is a distinct variable, and local to that execution only. When backtrack returns, you still have the same comb as before doing comb+cur.
Conclusion, you don’t need to pop anything. What you added with +cur only affects what the recursive execution sees; it does not affect the comb variable in the current execution of the function.
Alternative
You could compare this with a version of the code where the call of pop() makes sense:
comb.append(i) # Now we DO mutate `comb` here
backtrack(i+1,comb)
comb.pop() # ... and need to revert that change.
2
When you are using comb + cur you are creating a new list. So when comb.pop() is called it pops from original comb list. Here is the fix
def combination(n, k):
combi = []
def backtrack(start, comb):
# print(comb)
if len(comb) == k:
combi.append(comb.copy())
return
for i in range(start, n + 1):
comb.append(i)
backtrack(i + 1, comb)
comb.pop()
# print(f"comb after: {comb}")
backtrack(1, [])
return combi
print(combination(4, 3))
1