recursion - permutation in C++

Question

class Solution {
public:
     vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int> > result;
        vector<int> sofar;
        permutehelper(nums, sofar, result);
        return result;
    }
    
    void permutehelper(vector<int> &rest, vector<int> &sofar, vector<vector<int>> &ans){
                
        if(rest.size() == 0) {
            ans.push_back(sofar);
        }
        else{
            for(int i = 0; i < rest.size(); i++){
                sofar.push_back(rest[i]);
                rest.erase(rest.begin() + i);
                permutehelper(rest, sofar, ans);
            }
        }
    }
};    

How do I modify it to return all permutation, Currently it is giving only [[1,2,3]]. I know there are many solutions but I want to make it work using vectors sofar and rest.

question from:https://stackoverflow.com/questions/65713644/permutation-in-c

Answer 1

You only have one rest vector (and only one sofar vector) because you are passing by reference. That means that when you remove an element from rest, it's gone. You never put it back, so it's gone forever. (In fact, you're removing elements from the vector passed as an argument to permute. Some would say that modifying the argument is poor interface design.)

You probably want to pass the parameter vectors by value (other than ans, which accumulates results and thus should be permanently modified). Of course, passing by value makes copies, which introduces an unnecessary quadratic complexity, but it will allow the algorithm to work as expected.