Combination Sum python recursion scope

Question

I implemented a combination sum algorithm to the following problem:

# Given an array: [10,1,2,7,6,1,5]
# and a target: 8
# Find the solution set that adds up to the target
# in this case:
# [1, 7]
# [1, 2, 5]
# [2, 6]
# [1, 1, 6]

def cominbationSum(arr, target):
    arr =sorted(arr)
    res = []
    path = []
    dfs_com(arr, 0, target, path, res)
    return res

def dfs_com(arr, curr, target, path, res):
    if target == 0:
        res.append(path)
        return
    if target < 0:
        return
    for i in range(curr, len(arr)):
        if i > curr and arr[i] == arr[i-1]: # skip duplicates
            continue
        path.append(arr[i])
        dfs_com(arr, i+1, target - arr[i], path, res)
        path.pop(len(path)-1)


print cominbationSum([10,1,2,7,6,1,5], 8)

My algorithm generates the proper combinations, but it has a problem returning res. It returns res as [[],[],[],[]] rather than [[1, 1, 6],[1, 2, 5],[1, 7],[2, 6]]. Any idea why path isn't appending to res properly?

What's the python version?

Kasravnd
– Kasravnd

2016-03-15 19:39:16 +00:00
Commented Mar 15, 2016 at 19:39 — Kasravnd
– Kasravnd, Commented Mar 15, 2016 at 19:39
@Kasramvd python 2.7

ApathyBear
– ApathyBear

2016-03-15 20:14:05 +00:00
Commented Mar 15, 2016 at 20:14 — ApathyBear
– ApathyBear, Commented Mar 15, 2016 at 20:14

Kevin · Accepted Answer · 2016-03-15 19:37:53Z

4

Looks like a reference issue. Try:

if target == 0:
    res.append(path[:])
    return

This will create a shallow copy of path, so any pop performed on path later in the code will have no effect on the lists inside res.

answered Mar 15, 2016 at 19:37

Kevin

76.5k13 gold badges141 silver badges168 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Brent Washburne · Accepted Answer · 2016-03-15 19:38:03Z

1

Change the line

res.append(path)

to

res.append(path[:])

so you are getting a copy of path instead of the path itself. The problem is because you are removing elements in this line:

path.pop(len(path)-1)

answered Mar 15, 2016 at 19:38

Brent Washburne

13.2k4 gold badges65 silver badges86 bronze badges

Collectives™ on Stack Overflow

Combination Sum python recursion scope

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related