python recursion pass by reference or by value?

Question

I am working the this problem on leetcode:

Given a set of distinct integers, nums, return all possible subsets.
input =[1,2,3]
output =[[],[3],[2],[2,3],[1],[1,3],[1,2],[1,2,3]]

I have the c++ solution, which is accepted, and then i coded exactly the same python solution.

class Solution(object):    
    def subsets(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        solutions = []
        self._get_subset(nums, 0, [], solutions)

        return solutions

    @staticmethod
    def _get_subset(nums, curr, path, solutions):
        if curr>= len(nums):
            solutions.append(path)
            return

        path.append(nums[curr])
        Solution._get_subset(nums, curr+1, path, solutions)

        path.pop()
        Solution._get_subset(nums, curr+1, path, solutions)

The output is now: [[],[],[],[],[],[],[],[]]

It seems it is the Python pass by reference/ pass by value causing the problem, but i can't figure out how. The same c++ code works alright:

class Solution {
public:
vector<vector<int>> subsets(vector<int>& nums) {
    vector<vector<int>> solutions;
    vector<int> path;

    _get_path(nums, 0, path, solutions);
    return solutions;
}

void _get_path(vector<int>& nums, 
               int curr,
               vector<int>& path,
               vector< vector<int> > &solutions)
{
    if(curr >= nums.size()){
        solutions.push_back(path);
        return; 
    }
    path.push_back(nums[curr]);
    _get_path(nums, curr+1, path, solutions);

    path.pop_back();
    _get_path(nums, curr+1, path, solutions);
}
};

path is passed by reference, so you are always only manipulating the same instance. pass path[:] to pass a copy that you can modify — njzk2
– njzk2, Commented Sep 14, 2016 at 0:33

Barry · Accepted Answer · 2016-09-14 00:33:35Z

12

The problem is here:

solutions.append(path)

in C++, vector::push_back makes a copy of path (internally). But in Python, everything is a reference. So you build up your solutions as a list of many references to the same path, which eventually gets reduced to nothing.

You want a copy:

solutions.append(list(path))

or:

solutions.append(path[:])

answered Sep 14, 2016 at 0:33

Barry

312k32 gold badges734 silver badges1.1k bronze badges

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

Collectives™ on Stack Overflow

python recursion pass by reference or by value?

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related