引用与感谢
 
https://www.cnblogs.com/grandyang/p/4358848.html

1、全排列
 
问题描述
 
给定一个没有重复数字的序列，返回其所有可能的全排列。
 
示例:
 
输入: [1,2,3]
输出:
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]
 
解题思路
 
基本思路是递归加回溯。
这个问题转化为从左到右n个空行，n个数，每个数每次都只能使用一次，依次放入到所有的不同的n个空行中，返回所有的可能排列结果，即为全排列。使用函数递归和回溯法来解决这个问题。
随着递归的深入，直到元素序列只剩下最后两个时，将其交换。递归回退到上一层。随着循环，将在该层递归的前提下，序列从左到右依次与该层递归中的序列第一个元素交换，每交换一次后，再次进入递归将这这种情况下的所有可能结果随着递归排列完毕。在以该层递归的所有情况排列完毕后，递归函数回退到再上一层，再进行漫长地以该层递归为首的元素与其后面的所有元素交换再递归。以此类推，直到整个序列中的第一个元素与所有元素交换完毕并依次完成所有全排列后，算法结束，全排列完成。
下图是LeetCode中的官方题解中的动态图。
 
 
代码实现
 
class Solution {
public:
    void backtrack(vector<vector<int>>& res, vector<int>& nums, int index, int len){
        if (index == len) {
            res.push_back(nums);
            return;
        }
        for (int i = index; i < len; i++) {
            // 动态维护数组
            swap(nums[i], nums[index]);
            // 继续递归填下一个数
            backtrack(res, nums, index + 1, len);
            // 撤销操作
            swap(nums[i], nums[index]);
        }
    }
    vector< vector<int> > permute(vector<int>& nums) {
        vector< vector<int> > res;
        int len = nums.size();
        backtrack(res, nums, 0, len);
        return res;
    }
};
//他如果输入的是{1, 2, 3}的话，打印结果是：
/*
1 2 3
1 3 2
2 1 3
2 3 1
3 2 1
3 1 2
请按任意键继续. . .
*/
 
运行截图
 
 
在VS2013上的运行情况
 
#include<iostream>
#include<vector>
#include<algorithm>
using namesapce std;

void backtrack(vector< vector<int> > &res, vector<int> &nums, int index, int len){
	if (index == len){
		res.push_back(nums);
		return;
	}
	for (int i = index; i < len; i++){
		swap(nums[i], nums[index]);
		backtrack(res, nums, index + 1, len);
		swap(nums[i], nums[index]);
	}
}

vector< vector<int> > permute(vector<int>& nums){
	vector< vector<int> > res;
	int len = nums.size();
	backtrack(res, nums, 0, len);
	return res;
}

void main()
{
	vector< vector<int> > res;
	vector<int> nums = { 1, 2, 3, 4 };
	res = permute(nums);
	for (int i = 0; i < res.size(); i++){
		for (int j = 0; j < res[i].size(); j++){
			cout << res[i][j] << " ";
		}
		cout << endl;
	}
	system("pause");
	return;
}
/*
1 2 3 4
1 2 4 3
1 3 2 4
1 3 4 2
1 4 3 2
1 4 2 3
2 1 3 4
2 1 4 3
2 3 1 4
2 3 4 1
2 4 3 1
2 4 1 3
3 2 1 4
3 2 4 1
3 1 2 4
3 1 4 2
3 4 1 2
3 4 2 1
4 2 3 1
4 2 1 3
4 3 2 1
4 3 1 2
4 1 3 2
4 1 2 3
请按任意键继续. . .
*/
 
2、全排列 II
 
问题描述
 
给定一个可包含重复数字的序列，返回所有不重复的全排列。
 
示例:
 
输入: [1,1,2]
输出:
[
  [1,1,2],
  [1,2,1],
  [2,1,1]
]
 
解题思路
 
两种思路，提交结果时间复杂度都差不多。分别是在存储结束后去重和在存储的过程中使用集合来去重。???
 -思路改天再缕缕。
 
代码实现（1）
 
class Solution {
public:
    vector<vector<int>> ans;
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        dfs(nums, 0);
        return ans;
    }

    void dfs(vector<int> nums, int idx) {
        int n = nums.size();
        if (idx == n) 
        	ans.emplace_back(nums);

        unordered_set<int> s;
        for (int i = idx; i < n; ++i) {
            if (s.find(nums[i]) != s.end()) 
            	continue; //剪枝
            s.insert(nums[i]);

            vector<int> tmp = nums;
            swap(tmp[idx], tmp[i]);
            dfs(tmp, idx + 1);  
        }
    }
};
 
运行截图
 
 
代码实现（2）
 
class Solution {
public:

    void backtrack(vector< vector<int> >& res, vector<int> & nums, int index, int len){
        if(index == len){
            res.push_back(nums);
            return;
        }
        for(int i = index; i < len; i++){
            if((i + 1) != len and nums[i] == nums[i + 1])
                continue;
            swap(nums[i], nums[index]);
            backtrack(res, nums, index + 1, len);
            swap(nums[i], nums[index]);
        }
    }

    vector<vector<int>> permuteUnique(vector<int>& nums) {
        vector< vector<int> > res;
        sort(nums.begin(), nums.end());
        int len = nums.size();
        backtrack(res, nums, 0, len);
        sort(res.begin(), res.end());
        vector< vector<int> >::iterator iter = res.begin();
        iter = unique(res.begin(), res.end());
        vector< vector<int> > ans(res.begin(), iter);
        return ans;
    }
};
 
运行截图
 
 
3、第k个排列
 
问题描述
 
给出集合[1,2,3,…,n]，其所有元素共有n!种排列。
 
按大小顺序列出所有排列情况，并一一标记，当n = 3时, 所有排列如下：
 
"123"
"132"
"213"
"231"
"312"
"321"
给定 n 和 k，返回第 k 个排列。
 
说明：
 
给定 n 的范围是 [1, 9]。
给定 k 的范围是[1,  n!]。
 
示例 1:
 
输入: n = 3, k = 3
输出: "213"
 
示例 2:
 
输入: n = 4, k = 9
输出: "2314"
 
解题思路
 
首先用vector容器存储1到n数字。
定义一个计算阶乘的函数，用于计算每位的阶乘数。
k值对n-1位的阶乘数取整，该整数就是第一位应该从vector中所取数字的下标。
将该作为下标的数字所对应的vector容器取出，存放到string容器中，将该数字从vector中移除。
(k-1)值对n-1位的阶乘数取余即为下一轮循环中的开始k值，每次循环n减1，直到n为0为止。
k-1是边界的一个处理，比如n=4,k=6时，输出的排列字符串应该是1开头的排列的最后一个，如果用k/(n-1)!的话，则会输出第一个字符为2，所以，统一使用(k-1)/(n-1)!。因为用的是闭区间[]，不减1的话边界统一不起来，会成为[)。
 
代码实现
 
class Solution {
public:
    int getnum(int n){ // 求阶乘函数
        int ans = 1;
        for(int i = 1; i <= n; i++)
            ans *= i;
        return ans;
    }
    string getPermutation(int n, int k) {
        vector<int> v;   
        for(int i = 1; i <= n; i++)   
            v.push_back(i);
        string ans;
        while(n){
            int t = (k - 1) / getnum(n - 1);  
            ans += to_string(v[t]);
            v.erase(v.begin() + t);
            k -= (t * getnum(n - 1));
            n--;
        }
        return ans;
    }

};
 
运行截图
 
 
4、下一个排列
 
问题描述
 
实现获取下一个排列的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。
 
如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。
 
必须原地修改，只允许使用额外常数空间。
 
以下是一些例子，输入位于左侧列，其相应输出位于右侧列。
 
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1
 
解题思路
 
这种全排列的规则就是最开始是完全正序的，然后从右向左依次逐一去逆序，这也满足递归思想，后面的n个数全部为逆置序列说明穷举了所有排列可能，此时将倒数第n+1个数与后面的某一个进行交换，此时后面的n个数又将呈现为正序排列情况，以此类推，循环，直到序列中所有元素均为逆序。
所以，求第k个排列的下一个排列，就是从右向左找到第一个出现逆序的元素，用下标i来指向该元素，则说明i后面的素所有元素已经全部逆序，再次从右向左找到第一个大于等于nums[i]的元素，用下标j来指向，将其两两交换，nums[j]即为下一个需要跃进的元素。交换后，nums[j]后面的元素两端由右向左，由左向右，两两交换，即可把后面的逆序转化为正序。
 
代码实现
 
class Solution {
public:
    void reverse(vector<int>& nums, int start) {
        int i = start, j = nums.size() - 1;
        while (i < j) {
            swap(nums[i], nums[j]);
            i++;
            j--;
        }
    }
    void nextPermutation(vector<int>& nums) {
        int i = nums.size() - 2;
        while(i >= 0 and nums[i + 1] <= nums[i])
            i--;
        if(i >= 0){
            int j = nums.size() - 1;
            while(j >= 0 and nums[j] <= nums[i])
                j--;
            swap(nums[i], nums[j]);
        }
        reverse(nums, i + 1);
    }
};
 
运行截图
 

本文后续将更新解题思路以及优化解题方法
 
46. 全排列
 
难度中等
 
给定一个 没有重复 数字的序列，返回其所有可能的全排列。
 
示例:
 
输入: [1,2,3]
 
输出:
 
[
 
[1,2,3],
 
[1,3,2],
 
[2,1,3],
 
[2,3,1],
 
[3,1,2],
 
[3,2,1]
 
]
 
class Solution {

    public List<List<Integer>> permute(int[] nums) {

        LinkedList<List<Integer>> list = new LinkedList<>();

        permutation(list, nums, 0);

        return list;

    }

    public void permutation(LinkedList<List<Integer>> list, int[] nums, int n) {

        if (n == nums.length) {

            List<Integer> l = new LinkedList<>();

            for (int c : nums) {

                l.add(c);

            }

            list.add(l);

        } else {

            for (int i = n; i < nums.length; i++) {

                swap(nums, i, n);

                permutation(list, nums, n + 1);

                swap(nums, i, n);

            }

        }

    }



    public static void swap(int[] nums, int i, int n) {

        int temp = nums[n];

        nums[n] = nums[i];

        nums[i] = temp;

    }

}

 

  
 
47. 全排列 II
 
难度中等
 
给定一个可包含重复数字的序列，返回所有不重复的全排列。
 
示例:
 
输入: [1,1,2]
 
输出:
 
[
 
[1,1,2],
 
[1,2,1],
 
[2,1,1]
 
]
 
class Solution {

    public List<List<Integer>> permuteUnique(int[] nums) {

        ArrayList<List<Integer>> list = new ArrayList<>();

        permutation(list, nums, 0);

        return list;

    }

    public void permutation(List<List<Integer>> list,int[] nums,int n){

        if(n==nums.length){

            List<Integer> l = new ArrayList<>();

            for(int i:nums){

                l.add(i);

            }

            if(!list.contains(l)){

                list.add(l);

            }

        }else{

            for (int i = n; i < nums.length; i++) {

                swap(nums, i, n);

                permutation(list, nums, n + 1);

                swap(nums, i, n);

            }

        }

    }

    public void swap(int[] nums, int i, int n) {

        int temp = nums[n];

        nums[n] = nums[i];

        nums[i] = temp;

    }

}

 

  
 
60. 第k个排列
 
难度中等
 
给出集合 [1,2,3,…,n]，其所有元素共有 n! 种排列。
 
按大小顺序列出所有排列情况，并一一标记，当 n = 3 时, 所有排列如下：
 
 
"123"
 
 
"132"
 
 
"213"
 
 
"231"
 
 
"312"
 
 
"321"
 
给定 n 和 k，返回第 k 个排列。
 
说明：
 
 
给定 n 的范围是 [1, 9]。
 
 
给定 k 的范围是[1,  n!]。
 
示例 1:
 
输入: n = 3, k = 3
 
输出: "213"
 
示例 2:
 
输入: n = 4, k = 9
 
输出: "2314"
 
class Solution {

    public String getPermutation(int n, int k) {

        // n!

        int[] nums = new int[n + 1];

        nums[0] = 1;

        int sum = 1;

        for (int i = 1; i < n + 1; i++) {

            sum *= i;

            nums[i] = sum;

        }

        // 1-n

        ArrayList<Integer> list = new ArrayList<>();

        for (int i = 1; i < n + 1; i++) {

            list.add(i);

        }

        String result = "";

        k--;

        for (int i = 1; i <= n; i++) {

            int index = k / nums[n - i];

            result += list.get(index);

            list.remove(index);

            k = k % nums[n - i];

        }

        return result;

    }



}

 

  
 
31. 下一个排列
 
难度中等
 
实现获取下一个排列的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。
 
如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。
 
必须原地修改，只允许使用额外常数空间。
 
 
 
以下是一些例子，输入位于左侧列，其相应输出位于右侧列。
 
1,2,3 → 1,3,2
 
3,2,1 → 1,2,3
 
1,1,5 → 1,5,1
 
class Solution {

    public void nextPermutation(int[] nums) {

        int p = -1;

        for (int i = nums.length - 1; i >= 1; i--) {

            if (nums[i] > nums[i - 1]) {

                p = i - 1;

                break;

            }

        }

        if (p == -1) {

            reverse(nums, 0, nums.length - 1);

            return;

        }

        int q = -1;

        for (int i = nums.length - 1; i > p; i--) {

            if (nums[i] > nums[p]) {

                q = i;

                break;

            }

        }

        swap(nums, p, q);

        reverse(nums, p + 1, nums.length - 1);

    }



    public void swap(int[] nums, int i, int j) {

        int temp;

        temp = nums[i];

        nums[i] = nums[j];

        nums[j] = temp;

    }



    public void reverse(int[] nums, int i, int j) {

        while (i < j) {

            swap(nums, i, j);

            i++;

            j--;

        }

    }

}
 
78. 子集
 
难度中等
 
给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
 
说明：解集不能包含重复的子集。
 
示例:
 
输入: nums = [1,2,3]
 
输出:
 
[
 
[3],
 
[1],
 
[2],
 
[1,2,3],
 
[1,3],
 
[2,3],
 
[1,2],
 
[]
 
]
 
class Solution {

    public List<List<Integer>> subsets(int[] nums) {

        List<List<Integer>> result = new ArrayList<>();

        for (int i = 1; i <(int)Math.pow(2, nums.length);i++){

            char[] chs = toBinary(i, nums.length).toCharArray();

            ArrayList<Integer> l = new ArrayList<>();

            for (int j = 0; j < nums.length; j++) {

                if (chs[j] == '1') {

                    l.add(nums[j]);

                }

            }

            result.add(l);

        }

        result.add(new ArrayList<>());

        return result;

    }



    public String toBinary(int num, int digits) {

        String cover = Integer.toBinaryString(1 << digits).substring(1);

        String s = Integer.toBinaryString(num);

        return s.length() < digits ? cover.substring(s.length()) + s : s;

    }

}
 
 
 
90. 子集 II
 
难度中等
 
给定一个可能包含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
 
说明：解集不能包含重复的子集。
 
示例:
 
输入: [1,2,2]
 
输出:
 
[
 
[2],
 
[1],
 
[1,2,2],
 
[2,2],
 
[1,2],
 
[]
 
]
 
class Solution {

    public List<List<Integer>> subsetsWithDup(int[] nums) {

        Arrays.sort(nums);

        List<List<Integer>> result = new ArrayList<>();

        for (int i = 1; i < (int) Math.pow(2, nums.length); i++) {

            char[] chs = toBinary(i, nums.length).toCharArray();

            ArrayList<Integer> l = new ArrayList<>();

            for (int j = 0; j < nums.length; j++) {

                if (chs[j] == '1') {

                    l.add(nums[j]);

                }

            }

            if (!result.contains(l)) {

                result.add(l);

            }

        }

        result.add(new ArrayList<>());

        return result;

    }



    public String toBinary(int num, int digits) {

        String cover = Integer.toBinaryString(1 << digits).substring(1);

        String s = Integer.toBinaryString(num);

        return s.length() < digits ? cover.substring(s.length()) + s : s;

    }

}
 
 
 
 

目录
 
1、编号30 Next Permutation
 2、编号44 Permutations
 3、编号45 Permutations II
 4、编号60 Permutation Sequence
 
 
1、编号30 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
 
寻找当前数字组合的下一个排列。从后往前用排序做。
 
 
void nextPermutation (vector<int> &num) {
    int i;
    int j = num.size()-1;
    
    for(i = num.size()-1; i > 0; i--){
        if(num[i-1] < num[i]) {
            while(num[i-1] >= num[j]) j--;
            swap(num[i-1], num[j]);
            sort(num.begin()+i, num.end());
            break;
        }
    }
    
    if(i==0) sort(num.begin(), num.end());
}
    
void swap(int &x, int &y){
    int tmp = x;
    x = y;
    y = tmp;
}


 
2、编号44 Permutations 
 
Given a collection of 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], and [3,2,1].
 
 
三重循环。
 
 
class Solution {
public:
    vector<vector<int> > permute(vector<int> &num) {                
        vector<vector<int>> result;  
        vector<int> initElem;
        
        sort(num.begin(), num.end());
        
        initElem.push_back(num[0]);
        result.push_back(initElem);
        for(int i = 1; i < num.size(); i++) result = Insert(result, num[i]);
        return result;                                              
    }                                                           
        
    vector<vector<int> > Insert(vector<vector<int>> result, int num){
        vector<vector<int>> r;
        for(int i = 0; i < result.size(); i++){
            for(int j = 0; j < result[i].size() + 1; j++){
                vector<int> tmp;
                tmp = result[i];
                tmp.insert(tmp.begin()+j, num);
                r.push_back(tmp);
            }
        }
        
        return r;
    }
};

 
 
3、编号45 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], and [2,1,1].
 
 
DFS
 
 
class Solution {
public:
    vector<vector<int>> permuteUnique(vector<int> &num) {  
        vector<vector<int>> result;  
        vector<int> oneResult; 
        vector<bool> visited(num.size(), 0);  
        
        if(num.size() == 0) return result;  
        
        sort(num.begin(), num.end()); 
        
        GeneratePermute(num, 0, visited, oneResult, result);  
        return result;  
    }  
    void GeneratePermute(vector<int> & num, int level, vector<bool>& visited, 
                vector<int>& oneResult, vector<vector<int> >& result) {  
        if(level == num.size())  {  
            result.push_back(oneResult);  
            return;  
        }  
        for(int i = 0; i< num.size(); i++)  {  
            if(visited[i] == false){  
                if(i > 0 && num[i] == num[i-1] && visited[i-1] == false)  
                    continue;  
                    
                visited[i] = true;  
                oneResult.push_back(num[i]);  
                
                GeneratePermute(num, level+1, visited, oneResult, result);  
                oneResult.pop_back();  
                visited[i] = false;  
            }  
        }  
    }  

 
 
4、编号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 resultString;
        vector<int> input;
        for(int i = 0; i < n; i++) input.push_back(i+1);
 
        if(input.size() == 0) return resultString;
        
        k--;/*!!!!!!!!*/
        
        while(input.size() > 1){
            int f = factorization(input.size()-1);
            int pos = k/f;
            resultString += input[pos] + '0';
            input.erase(input.begin() + pos);
            
            /*Update k*/
            k = k%f;
        }
        resultString += input[0] + '0';
        
        return resultString;
    }
    
    int factorization(int n){
        if(n == 0) return 1;
        int r = 1;
        for(int i = n; i > 0; i--) r *= i;
        return r;
    }

};


 
 
 
 参考文献：
 
 http://oj.leetcode.com/problems/