46.全排列

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

示例 1：

**输入：** nums = [1,2,3]
**输出：** [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

示例 2：

**输入：** nums = [0,1]
**输出：** [[0,1],[1,0]]

示例 3：

**输入：** nums = [1]
**输出：** [[1]]

提示：

• 1 <= nums.length <= 6
• -10 <= nums[i] <= 10
• nums 中的所有整数 互不相同

思路：

1. 设立一个辅助数组flag，用于标记每个元素是否已经添加过
2. 在递归中循环遍历需要添加的元素，若没有添加过，则添加并进行标记，然后进行下一轮递归，递归不是并发，不用考虑标记数组flag
3. 去掉已经刚刚添加的元素，进入下一轮循环。在下一轮循环的递归中，会将刚才去掉的元素遍历到。

class Solution {
    List<List<Integer>> ans=new ArrayList<>();
    public List<List<Integer>> permute(int[] nums) {
        int[] flag=new int[nums.length];
        backtrace(flag,nums,new ArrayList<Integer>());
        return ans;
    }
    public void backtrace(int[] flag,int[] nums,List<Integer> temp){
        if(temp.size()==nums.length){
            //添加时新建一个List
            ans.add(new ArrayList<>(temp));
            return;
        }
        for(int i=0;i<nums.length;i++){
            if(flag[i]==0){
                temp.add(nums[i]);
                flag[i]=1;
                //递归需放在if里面
                backtrace(flag,nums,temp);
                temp.remove(temp.size()-1);
                flag[i]=0;
            }
        }
    }
}