Python program to generate all possible unique ways to represent n=3 as sum of positive integers:
def fun():
res=[]
a=[]
def backtracking(n):
if(n==0):
res.append(a)
print(res)
return
if(n<0):
return
for i in range(1,n+1):
a.append(i)
backtracking(n-i)
a.pop()
backtracking(3)
return res
print(fun())
Expecting res = [[1,1,1][1,2][2,1][3]]
instead getting [ [] [] [] [] ]
You are appending the list a
directly to the res
, you should be appending a copy of the list a
instead. List is passed by reference, so in the end, your res
has 4 references to the same list which is empty. To get a copy of the list you have different options - list.copy()
, copy.copy() method, or just slicing list[:]
def fun():
res=[]
a=[]
def backtracking(n):
if(n==0):
res.append(a.copy()) # updated
# print(res)
return
if(n<0):
return
for i in range(1,n+1):
a.append(i)
backtracking(n-i)
a.pop()
backtracking(3)
return res
print(fun())
Output:
[[1, 1, 1], [1, 2], [2, 1], [3]]