求一个数组的全排列。

遇到的问题：

1.忘记了字典序排列的定义；
2.思考时间过长；
3.没有及时找到全排列和字典序之间的关系；

想到的解题思路：

1.用字典序找到下一个排序；
2.全排序共有n!种组合，找够停止循环；

代码如下：

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
// 如果数组长度是零直接返回
        if(nums.length == 0)
            return ans;
//求数组全排列
        int n = nums.length;
        int sum = 1;
        for(int i=2;i<=n;i++)
            sum *=i;
        for(;sum>0;sum--){
            ans.add(nextPermutation(nums));
        }
        return ans;
    }
//按照字典序求下一个排列
    public List<Integer> nextPermutation(int[] nums){
        int flag = 0;
        int j = 0;
//从头开始找到比右边数字的小的数的最大序号j
        for(int i=0;i<nums.length-1;i++){
            if(nums[i]<nums[i+1]){
                flag = i;
                if(flag > j)
                    j = flag;
            }
        }
        List<Integer> l = new ArrayList<>();
        int k = 0;
//从j开始，找到比j大的最小的数的序号k
        for(int i=j+1;i<nums.length;i++){
            if(nums[i]>nums[j])
                k = i;
            else
                break;
            }
        if(k == 0)
            Arrays.sort(nums);
        else{
//交换j，k
            int tmp = nums[j];
            nums[j] = nums[k];
            nums[k] = tmp;
//倒置j+1到n-1之间的数得到字典序的下一个排列
            for(int i=1;i<=(nums.length-j-1)/2;i++){
                tmp = nums[nums.length-i];
                nums[nums.length-i] = nums[j+i];
                nums[j+i] = tmp;
            }
        }
        for(int i=0;i<nums.length;i++)
            l.add(nums[i]);
        return l;
    }
}

附加内容：

1.字典序的概念：

设P是1～n的一个全排列

1）从排列的右端开始，找出第一个比右边数字小的数字的序号j（j从左端开始计算），即 j=max{i|p_i<p_i+1}

2）在p_j的右边的数字中，找出所有比p_j大的数中最小的数字p_k，即 k=max{i|p_i>p_j}（右边的数从右至左是递增的，因此k是所有大于p_j的数字中序号最大者）

3）对换p_j，p_k

4）再将p_j+1......p_k-1p_kp_k+1......p_n倒转得到排列p'=p₁p₂.....p_j-1p_jp_n.....p_k+1p_kp_k-1.....p_j+1，这就是排列p的下一个排列。

2.全排列概念：

从n个不同元素中任取m（m≤n）个元素，按照一定的顺序排列起来，叫做从n个不同元素中取出m个元素的一个排列。当m=n时所有的排列情况叫全排列。
公式：全排列数f(n)=n!(定义0!=1)