I have some difficulties with understanding the space complexity of the following algorithm. I’ve solved this problem subsets on leetcode. I understand why solutions’ space complexity would be O(N * 2^N), where N – the length of the initial vector. In all those cases all the subsets (vectors) are passed by value, so we contain every subset in the recursion stack. But i passed everything by reference. This is my code:

`class Solution { public: vector<vector<int>> result; void rec(vector<int>& nums, int &position, vector<int> ¤tSubset) { if (position == nums.size()) { result.push_back(currentSubset); return; } currentSubset.push_back(nums[position]); position++; rec(nums, position, currentSubset); currentSubset.pop_back(); rec(nums, position, currentSubset); position--; } vector<vector<int>> subsets(vector<int>& nums) { vector <int> currentSubset; int position = 0; rec(nums, position, currentSubset); return result; } }; `

Would the space complexity be O(N)? As far as i know, passing by reference doesn’t allocate new memory, so every possible subset would be contained in the same vector, which was created before the recursion calls.

I would also appreciate, if you told me how to estimate the space complexity, when working with references in general. Those are the only cases, where i hesitate about the correctness of my reasonings.

Thank you.