46. 全排列

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        used = new boolean[nums.length];
        recur(0,nums);
        return ans;
    }
    boolean[] used;
    List<Integer> chosen = new ArrayList<>();
    int pos;
    List<List<Integer>> ans = new ArrayList<>();
    public void recur(int pos,int[] nums){
        //1:循环结束条件，当位置 = 数组长度的时候，保存当前已经选择的数组
        if(pos == nums.length){
            ans.add(new ArrayList<>(chosen));
            return;
        }
        // 2: 递归方法，也就是相似的方法
        for(int i = 0;i < nums.length;i++){
            if(!used[i]){
                chosen.add(nums[i]);
                used[i] = true;
                recur(pos + 1,nums);
                //3：还原现场
                chosen.remove(chosen.size()-1);
                used[i] = false;
            }
        }
    }
}