题解 | #没有重复项数字的全排列#

方法一：递归+回溯

全排列就是要交换数组中元素位置所能得到的全部解，题目要求按字典序从小到大排列，则排序后的数组是字典序最小的，此后就保持前面的元素不变交换后面的元素，这个时候就用到了递归。

• 递归终止条件是：遍历到最后一个位置，则添加当前顺序到结果数列。
• 本级递归任务是：向后遍历，交换当前index位置与本次循环下标，然后递归。

只用递归不够，应该加上回溯，使回到上一个子问题，使考虑到在此问题的基础上的所有情况。

综上，步骤如下：

1、数组排序，得到字典序最小的情况

2、交换位置的值，向下递归

3、交换，回溯，进入下一分支

4、数组结尾，添加结果，返回继续遍历，直到所有情况遍历结束

import java.util.*;
public class Solution {
    //a,b为下标
    private void swap(ArrayList<Integer> num,int a,int b){
        int temp =num.get(a);  //获取指定下标位置的值
        num.set(a,num.get(b));  //设置指定位置的值
        num.set(b,temp);
    }
    public void recursion( ArrayList<ArrayList<Integer>> res,ArrayList<Integer> array,int index){
        //分支进入结尾，说明已经找到一种排列
        if(index == array.size()-1){
            res.add(array);
            return;
        }
        //遍历后续元素
        for(int i=index;i<array.size();++i){
            swap(array,i,index);
            recursion(res,array,index+1);
            //将交换的情况换回来再回溯
            swap(array,i,index);
        }
    }
    public ArrayList<ArrayList<Integer>> permute (int[] num) {
        //排序
        Arrays.sort(num);
        ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
        ArrayList<Integer> array = new ArrayList<Integer>();
        //数组转为ArrayList
        for(int i=0;i<num.length;++i){
            array.add(num[i]);
        }
        //递归
        recursion(res,array,0);
        return res;
    }
}