Home > Back-end >  Subset algorithm behaves differently in Python than C
Subset algorithm behaves differently in Python than C

Time:10-12

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

  1. In first recursion the first part is neglected
  2. 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

CodePudding user response:

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
  • Related