46.Permutations
Given a collection of distinct numbers, return all possible permutations.
For example,
[1,2,3] have the following permutations:

[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

代碼如下：

class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> rec;
        if(nums.size()<=0)
          return rec;
        dfs(nums,0,rec);
        return rec;
    }
    
    void dfs(vector<int>& nums,int start,vector<vector<int>>& rec)
    {
        if(start==nums.size())
        {
            rec.push_back(nums);
        }
        else
        {
            for(int i=start;i<nums.size();i++)
            {
                swap(nums[start],nums[i]);
                dfs(nums,start+1,rec);
                swap(nums[start],nums[i]);
            }
        }
    }
};

**47.Permutations II **
Given a collection of numbers that might contain duplicates, return all possible unique permutations.

For example,
[1,1,2] have the following unique permutations:

[
  [1,1,2],
  [1,2,1],
  [2,1,1]
]

代碼如下：

class Solution {
public:
    set<vector<int>> mSet;
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        vector<vector<int>> rec;
        if(nums.size()<=0)
          return rec;
        sort(nums.begin(),nums.end());
        dfs(nums,0);
        for(auto a:mSet)
          rec.push_back(a);
        //return vector<vector<int>>(mSet.begin(),mSet.end());
        return rec;
    }
    
    void dfs(vector<int>& nums,int start)
    {
        if(start==nums.size())
        {
            mSet.insert(nums);
            //rec.push_back(nums);
        }
        else
        {
            for(int i=start;i<nums.size();i++)
            {
                //if(i!=start&&nums[i]==nums[i-1])
                //  continue;
                swap(nums[start],nums[i]);
                dfs(nums,start+1);
                swap(nums[start],nums[i]);
            }
        }
    }
};

**31.Next Permutation **
Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.

If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).

The replacement must be in-place, do not allocate extra memory.

Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

代碼如下：

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        int n = nums.size();
        if(n<=0)
          return;
        int pivot = -1;  
        int i = n-1;
        for(;i>=1;i--)   //從右到左，先找出數(shù)組中非增序序列乳规，找到這個序列最大值左邊的一個數(shù)A
        {                //并找出該非遞增序列中比A大的最少的值B形葬，交換兩個數(shù)的值，然后對該遞增序列排序
            if(nums[i]>nums[i-1])
            {
                pivot = i-1;
                break;
            }
        }
        if(pivot>=0)
        for(int j=n-1;j>=0;j--)
        {
            if(nums[j]>nums[pivot])
            {
                int temp = nums[j];
                nums[j] = nums[pivot];
                nums[pivot] = temp;
                sort(nums.begin()+pivot+1,nums.end());  //牢牢記住特殊的規(guī)則
                return;
            }
            
        }
        else
        {
            sort(nums.begin(),nums.end());
        }
        return;
    }
};

**60. Permutation Sequence **
The set [1,2,3,…,n] contains a total of n! unique permutations.

By listing and labeling all of the permutations in order,
We get the following sequence (ie, for n = 3):

"123"
"132"
"213"
"231"
"312"
"321"

Given n and k, return the kth permutation sequence.
Note: Given n will be between 1 and 9 inclusive.
代碼如下：

class Solution {
public:
    string getPermutation(int n, int k) {
        string rec = "";
        vector<int> num(10,0);
        for(int i=0;i<n;i++)
        {
            num[i] = i + 1;
        }
        
        k--;
        for(int i=n;i>=1;i--)
        {
            int j = k/getFac(i-1); 
            k %= getFac(i-1);       //除去非目標數(shù)字為首的字符串所占的位數(shù)
            rec += to_string(num[j]);
            for(int k=j;k<n-1;k++)
            {
                num[k] = num[k+1];  //把可選數(shù)字左移
            }
        }
        return rec;
        
    }
    int getFac(int t)
    {
        int result=1;
        while(t>0)
        {
            result *= t;
            t--;
        }
        return result;
    }
};