题解 | #没有重复项数字的全排列#递归+回溯+排序

public class Solution {
    public ArrayList<ArrayList<Integer>> permute(int[] num) {
        //思路：利用递归
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
        if(num == null || num.length == 0){
            return res;
        }
        //先对数组进行排序
        Arrays.sort(num);
        doWork(res,num,0);
        return res;
    }
    
    private void doWork(ArrayList<ArrayList<Integer>> res,int[] num,int index){
        if(index == num.length - 1){
            //数组转list
            ArrayList<Integer> list = new ArrayList<>();
            for(int i = 0;i<num.length;i++){
                list.add(num[i]);
            }
            res.add(list);
        } else {
            for(int i = index;i<num.length;i++){
                swap(num,index,i);
                int[] afterOrder = new int[num.length];
                for(int j = 0;j<num.length;j++){
                    afterOrder[j] = num[j];
                }
                quickOrder(afterOrder,index + 1,afterOrder.length - 1);
                doWork(res,afterOrder,index + 1);
                swap(num,i,index);
            }
        }
    }
    
    private void swap(int[] num,int index,int i){
        int temp = num[i];
        num[i] = num[index];
        num[index] = temp;
    }
    
    private void quickOrder(int[] num,int begin,int end){
        if(begin >= end){
            return;
        }
        int left = begin;
        int right = end;
        int res = num[left];
        while(left < right){
            while(left < right && num[right] > res){
                right --;
            }
            if(left < right){
                num[left] = num[right];
                left ++;
            }
            while(left < right && num[left] < res){
                left ++;
            }
            if(left < right){
                num[right] = num[left];
                right --;
            }
        }
        num[left] = res;
        quickOrder(num,begin,left - 1);
        quickOrder(num,left + 1,end);
    }
}