lintcode 15 全排列

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++){//遍历整个数组
                swap(nums[begin],nums[i]);//把被遍历的数放在首位
                help(res,begin+1,end,nums);//求首位之后的所有排列情况
                swap(nums[begin],nums[i]);//恢复原始数组
            }
        }
    }
    void swap(int& a,int& b){
        int temp = a;
        a = b;
        b = temp;
    }
};

递归算法思路：对数据[1,2,3]，需要一次遍历；每次遍历，确定首位，[1,...];[2,...];[3,...]然后通过递归得到后面的所有排列情况，对于数组中有重复元素的情况，我们只要保证，重复元素只能有一次作为子问题的开头元素，这样我们就可以避免重复计算。

非递归算法思路：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;
    }
};