class Solution {
public:
    /*
     * @param nums: A list of integers.
     * @return: A list of permutations.
     */
    vector<vector<int>> permute(vector<int> &nums) {
        // write your code here
        vector<vector<int>> res;
        if(nums.size() < 2)
        {
            res.push_back(nums);
            return res;
        }
        help(res,0,nums.size(),nums);
        return res;
    }
    
    void help(vector<vector<int>>& res,int begin,int end,vector<int> &nums)//得到從begin開始的全排列
    {
        if(begin == end){                      //基本情況  
            res.push_back(nums);             
        }else{
            for(int i = begin;i < end;i++){//遍歷整個數(shù)組
                swap(nums[begin],nums[i]);//把被遍歷的數(shù)放在首位
                help(res,begin+1,end,nums);//求首位之后的所有排列情況
                swap(nums[begin],nums[i]);//恢復(fù)原始數(shù)組
            }
        }
    }
    void swap(int& a,int& b){
        int temp = a;
        a = b;
        b = temp;
    }
};

遞歸算法思路：對數(shù)據(jù)[1,2,3]，需要一次遍歷；每次遍歷，確定首位，[1,...];[2,...];[3,...]然后通過遞歸得到后面的所有排列情況，對于數(shù)組中有重復(fù)元素的情況，我們只要保證，重復(fù)元素只能有一次作為子問題的開頭元素，這樣我們就可以避免重復(fù)計算。

非遞歸算法思路：https://www.cnblogs.com/answeryi/archive/2011/10/12/2209058.html
字典排序 注意 逆序的步驟不要錯過

class Solution {
public:
    /*
     * @param nums: A list of integers.
     * @return: A list of permutations.
     */
    vector<vector<int>> permute(vector<int> &nums) {
        // write your code here
        vector<vector<int>> res;
        if(nums.size() < 2){
            res.push_back(nums);
            return res;
        }
        sort(nums.begin(),nums.end());
        int point = -1;
        res.push_back(nums);
        while((point = findpoint(nums)) != -1){
            int next = findnext(nums,point);
            swap(nums[point-1],nums[next]);
            diandao(nums,point);
            res.push_back(nums);
        }
        return res;
    }
    int findpoint(vector<int> &nums){
        int len =  nums.size();
        for(int i = len-1;i >0;i--){
            if(nums[i] > nums[i-1])
                return i;
        }
        return -1;
    }
    int findnext(vector<int> &nums,int point){
        int len  = nums.size();
        int i  = 0;
        for(i = point; i < len;i++){
            if(nums[point-1] > nums[i]){
                return i-1;
            }
        }
        return i-1;
    }
    void  diandao(vector<int> &nums,int point){
        int j = nums.size()-1;
        int i = point;
        while(i < j){
            swap(nums[i],nums[j]);
            i++;
            j--;
        }
    }
    void swap(int& a,int& b){
        int temp;
        temp = a;
        a = b;
        b = temp;
    }
};