A different recursive C++ solution : 20ms


  • 0
    N
    class Solution {
    public:
        vector<vector<int>> ans;
        
        void tail(vector<int> input, vector<int> temp){
            int length=input.size();
            vector<int> inu=input;
            vector<int> tempo=temp;
    
            if(length==1){ //base case
                temp.push_back(input[0]);
                ans.push_back(temp);
            }
            else{
                for(int i=0;i<length;i++){
                    temp.push_back(input[i]);
                    input.erase(input.begin()+i);
    
                    tail(input,temp); //recursive call
    
                    temp=tempo; //setting things back to as they were.
                    input=inu;
                }
            }
        }
        vector<vector<int>> permute(vector<int>& nums) {
            vector<int> temp1;
            tail(nums,temp1);            
            return ans;
        }
    };

  • 0

    Good joke......


  • 0
    N

    why do u feel so?


  • 0

    Well because it's funny, of course.

    Just to be sure: You call it "tail recursion" because the function is called "tail" and because it's recursive, not because you think it's actual tail recursion, right?


  • 0
    N

    Well I named it as "tail" for clarity. If you trace (for example:123), you will come to know that with recursive calls I am decreasing elements from "input" and adding them in "temp". Ain't that tail recursion? And after I get one permutation I add this 2nd argument "temp" which collects permutation to "ans". Also in different order to get permutations.


  • 0

    I don't see how that has anything to do with tail recursion. Tail recursion is when the recursive call is the last thing you do before you return. It allows some optimizations because things aren't needed anymore. You on the other hand continue doing stuff after the call, even in a loop, and you even explicitly keep and restore a lot of state. You even explicitly document it in a comment. Seems pretty much like an extreme opposite of tail recursion. That's why I found it funny in the first place. Did you check out the wikipedia article at all?


  • 0
    N

    Sorry, I messed up my concept of tail recursion. I thought tail recursion is only limited to storing result in argument of recursive function but there is much more to it. Yes you are correct about storing of states. In tail recursion we don't do that and it is usually the last thing before return. So I guess my solution is just a different recursive approach and not a tail recursive. Thanks for your comments. I have made necessary changes to title and comments in code.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.