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

思路:
1.先固定第一位，然后第二位有n-1种可能，第三位有n-2种可能
2.如何实现？用for循环遍历，i = 0 到 n-1 ，当第一位是i=0时，第二位再用for循环从 1 到n-1选择，当第二位是i=1时，第三位从2到n-1种选择
3.每种排列去重
4.递归边界条件，排列组合大小为数组大小时，即一个排列。然后再向前回溯一位，再排列

import java.util.*;

public class Solution {
    public ArrayList<ArrayList<Integer>> permute(int[] num) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<>();
        
        LinkedList<Integer> list = new LinkedList<>();
        
        backTrack(num,list,result);
        return result;
    }
    private void backTrack(int[] num, LinkedList<Integer> list, ArrayList<ArrayList<Integer>> result){
        //终止条件，list为全排列的某一种组合
        if(list.size() == num.length){
            result.add(new ArrayList<Integer>(list));
            return;
        }
        for(int i = 0; i< num.length; i++){
            //去重
            if(list.contains(num[i])){
                continue;
            }
            //固定第一个数，有num.length种可能(不包含去重的话)
            list.add(num[i]);
            //第二个数有num.length -1 种可能
            backTrack(num, list, result);
            //向前不断回溯，当第n-1位选择后，这里将移除n-1位，然后向上回溯，又会将n-2位也移除，然后n-2位for循环遍历到n-1位，再递归
            list.removeLast();
        }
    }
}