T46、全排列

给定一个没有重复数字的序列，返回其所有可能的全排列。
示例:
输入: [1,2,3]
输出:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]

解

使用回溯算法，问题可以转化为生成一棵树，树的每一个路径都是一个有效的排列，为了防止出现重复的数字，使用一个used数组记录数字是否已经访问，记录完之后，需要弹出该数字并标记为未访问。

public static List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        int len = nums.length;
        boolean[] used = new boolean[len];
        if(0==len)
            return res;
        
        generatePermution(nums,used,0,len,new Stack<>(),res); 
        return res;    
    }
    
    public static void generatePermution(int []nums,boolean[] used,int current,int len,Stack<Integer> path,List<List<Integer>> res) {
        if(current == len) {
            //找到一个排列
            res.add(new ArrayList<>(path));
            return;
        }
        
        for(int i = 0;i<len;i++) {
            if(!used[i]) {
                path.push(nums[i]);
                used[i] = true;
                generatePermution(nums,used,current+1,len,path,res);
                //返回上一个节点 记得标记为未访问
                path.pop();
                used[i] = false;
            }
        }
    }