【LeetCode刷题-回溯】-- 46.全排列

46.全排列

方法：回溯法

一种通过探索所有可能的候选解来找出所有的解的算法，如果候选解被确认不是一个解，回溯法会通过在上一步进行一些变化抛弃该解，即回溯并且再次尝试

使用一个标记数组表示已经填过的数

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        List<Integer> output = new ArrayList<Integer>();

        int n = nums.length;
        boolean[] visited = new boolean[n];
        backtrack(res,output,visited,nums);
        return res;
    }
    public void backtrack(List<List<Integer>> res,List<Integer> output,boolean[] visited,int[] nums){
        if(output.size() == nums.length){
            res.add(new ArrayList(output));
            return;
        }
        for(int i = 0;i<nums.length;i++){
            if(!visited[i]){
                output.add(nums[i]);
                visited[i]=true;
                backtrack(res,output,visited,nums);
                //退到上一状态
                visited[i]=false;
                output.remove(output.size()-1);
            }
        }
    }
    
}