剑指OFFER的一道关于全排列的题目，我这样写为何得到了正确的结果，感觉想了想挺不符合逻辑的。

Question

题目：

我刚开始的代码（能AC）：

class Solution {
public:
    vector<string> Permutation(string str) {
        vector<string> v;
        if(str.empty())
            return v;
        return permuta(v,str,0);
    }
    vector<string> permuta(vector<string> &v,string str,int n)
    {
        if(n==str.size())
            v.push_back(str);
        else
            {
                permuta(v,str,n+1);             
                for(int i=n+1;i<str.size();i++)  
                {    
                    if(str[i]!=str[n])           
                    {
                        swap(str[n],str[i]);
                        permuta(v,str,n+1);
                    }   
                }
            }         
            return v;
     }     
};

之后修改的代码，符合逻辑也能AC，想不通第一种为什么能直接实现全排列了

class Solution {
public:
    vector<string> Permutation(string str) {
        vector<string> v;
        if(str.empty())
            return v;
        permuta(v,str,0);
        sort(v.begin(),v.end());   
        return v;
    }
    void permuta(vector<string> &v,string str,int n)
    {
        if(n==str.size())
            v.push_back(str);
        else
            {
                permuta(v,str,n+1);              
                for(int i=n+1;i<str.size();i++)  
                {    
                    if(str[i]!=str[n])           
                    {
                        swap(str[n],str[i]);
                        permuta(v,str,n+1);
                        swap(str[n],str[i]);     
                    }   
                }
            }         
    }   
};

VS2019中能直接测试的代码放在下面：

#include <bits/stdc++.h>
using namespace std;
vector<string> v;
vector<string> permuta(vector<string>& v, string str, int n);
    vector<string> Permutation(string str)
    {

     if (str.empty())
            return v;
        return permuta(v, str, 0);
    }
    vector<string> permuta(vector<string>& v, string str, int n)
    {
        if (n == str.size())
            v.push_back(str);
        else
        {
            permuta(v, str, n + 1);              
            for (int i = n + 1; i < str.size(); i++)  
            {
                if (str[i] != str[n])           
                {
                    swap(str[n], str[i]);
                    permuta(v, str, n + 1);
                    //swap(str[n], str[i]);     
                }
            }
        }
        return v;
    }
int main()
{
    Permutation("abcd");
    return 0;
}

为什么更少的代码也AC了

Answer 1

string str每次调用都创建了一个新的副本
你permuta(v, str, n + 1);之后没有再用到str，所以无需恢复