[数据结构与算法]全排列(Java)

思路：
回溯法，终止条件为List长度为数组长度，使用数组标记当前下标是否已经被使用，回溯时remove一次List并使标记数组在当前下标下的状态为未使用
代码：

class Solution {
	//用来存放大结果
    List<List<Integer>> res = new ArrayList<>();
    
    public List<List<Integer>> permute(int[] nums) {
    	//调用回溯算法
        dfs(new ArrayList<>(),nums,new int[nums.length]);
        return res;
    }
    //temp用来存放每次的小结果，nums是输入的数组，isHave为标记数组
    public void dfs(List<Integer> temp,int[] nums,int[] isHave){
    	//终止条件
        if(temp.size() == nums.length){
        	//将小结果存放到大结果中
        	//注意：要重新new一个List，否则后续temp改变时res也会变
            res.add(new ArrayList<>(temp));
            return;
        }
   		//循环遍历数组
        for(int i = 0;i < nums.length; i++){
        	//如果该下标标记为1表示已被使用，直接下次循环
            if(isHave[i] == 1) continue;
            //如果未被使用则加到小结果中
            temp.add(nums[i]);
            //使该下标标记为已使用
            isHave[i] = 1;
            //递归调用回溯来找下一个数
            dfs(temp,nums,isHave);
            //回溯，清除temp
            temp.remove(temp.size() - 1);
            //标记数组初始化
            isHave[i] = 0;
        }
    }
}