Subset algorithm behaves differently in Python than C++

Question

The algorithm follows recursive approach, dividing the array in two parts:

In first recursion the first part is neglected
In second part the first part is added

Code for C++ (Works Fine)

class Solution {
public:
    
    vector<vector<int>> result;
    
    void get_set(vector<int>& nums, vector<int> res, int index=0)
    {
        if(index == nums.size())
        {
            result.push_back(res);
            return;
        }
        
        int top = nums[index++];
        
        get_set(nums, res, index);
        res.push_back(top);
        get_set(nums, res, index);
    }
    
    vector<vector<int>> subsets(vector<int>& nums) 
    {
        vector<int> res;
        
        get_set(nums, res);
        
        return result;
    }
};

Code for Python

class Solution:
def __init__(self):
    self.result = [[]]
    
def get_subsets(self, arr, temp=[], index=0):
    if(index==len(arr)):
        self.result.append(temp)
        return
    top = arr[index]
    index+=1
    
    self.get_subsets(arr, temp, index)
    temp.append(top)
    self.get_subsets(arr, temp, index)

def subsets(self, nums: List[int]) -> List[List[int]]:
    self.get_subsets(nums)
    return self.result

I suspect it's this: stackoverflow.com/questions/1132941/… — Barmar
– Barmar, Commented Oct 11, 2022 at 16:49
@Barmar not just that, actually, since I bet this is only run one time. The problem is that this keeps appending the same list to the result. But re-using the default argument will cause problems if get_subset is called again — juanpa.arrivillaga
– juanpa.arrivillaga, Commented Oct 11, 2022 at 16:52
Right, self.result.append(temp) is always the same list, which you keep appending to with temp.append(top). The C++ version makes copies of res on each call, because it's not a reference parameter. — Barmar
– Barmar, Commented Oct 11, 2022 at 16:54

Barmar · Accepted Answer · 2022-10-11 16:59:41Z

In the C++ version, res is a by-value parameter, so a copy of the vector is made in each call. Python passes references to the list, so you keep modifying the same temp list throughout the algorithm. Pass a copy when you make the recursive calls.

There's also no need for an empty nested list in the initial value of self.result. The C++ version starts with an empty vector.

class Solution:
    def __init__(self):
        self.result = []

    def get_subsets(self, arr, temp=None, index=0):
        if temp is None:
            temp = []
        if(index==len(arr)):
            self.result.append(temp)
            return
        top = arr[index]
        index+=1

        self.get_subsets(arr, temp.copy(), index)
        temp.append(top)
        self.get_subsets(arr, temp.copy(), index)

    def subsets(self, nums: List[int]) -> List[List[int]]:
        self.get_subsets(nums)
        return self.result

Collectives™ on Stack Overflow

Subset algorithm behaves differently in Python than C++

1 Answer 1

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related