Permutation 全排列

递归解决全排列（回溯法）

回溯法的思路也不难理解。
考察其如何递归，以1234为例。首先需要考虑第一位，可以以此与后续元素交换得到2-134， 3-214， 4-231.
然后对后三位递归地调用（与后续元素交换）即可。当递归到无法交换（就剩一位），则输出。

class Solution1{
public:
    vector<string> permute(string s){
        vector<string> result;
        helper(result, s, 0);
        return result;
    }

    void helper(vector<string>& result, string& s, int index){
        if(index == s.size()-1)
            result.push_back(s);
        for(int i = index; i<s.size(); ++i){
            swap(s[index],s[i]);
            helper(result, s, index+1);
            swap(s[index],s[i]);
        }
    }
};

考虑重复元素

由于全排列就是从第一个数字起每个数分别与它后面的数字交换。我们先尝试加个这样的判断——如果一个数与后面的数字相同那么这二个数就不交换了。如122，第一个数与后面交换得212、221。然后122中第二数就不用与第三个数交换了，但对212，它第二个数与第三个数是不相同的，交换之后得到221。与由122中第一个数与第三个数交换所得的221重复了。所以这个方法不行。

换种思维，对122，第一个数1与第二个数2交换得到212，然后考虑第一个数1与第三个数2交换，此时由于第三个数等于第二个数，所以第一个数不再与第三个数交换。再考虑212，它的第二个数与第三个数交换可以得到解决221。此时全排列生成完毕。

这样我们也得到了在全排列中去掉重复的规则——去重的全排列就是从第一个数字起每个数分别与它后面非重复出现的数字交换。用编程的话描述就是第i个数与第j个数交换时，要求[i,j)中没有与第j个数相等的数。下面给出完整代码：

class mySolution02{
public:

    bool isduplicate(string& s, int start, int end){
        for(int i = start ; i<end; ++i){
            if(s[i] == s[end])
                return true;
        }
        return false;
    }
    vector<string> permute(string s){
        sort(s.begin(), s.end());
        vector<string> result;
        helper(result, s, 0);
        return result;
    }

    void helper(vector<string>& result, string& s, int index){
        if(index == s.size()-1)
            result.push_back(s);
        for(int i = index; i<s.size(); ++i){
            if(isduplicate(s, index, i))
                continue;
            swap(s[index],s[i]);
            helper(result, s, index+1);
            swap(s[index],s[i]);
        }
    }
};