46. 全排列

全排列问题

思路

使用回溯来解决

第一步是从这三个元素中抽出一个元素，接下来递归求解，继续在其中抽出一个元素

依次可得

使用回溯法来解决问题

code

class Solution {
    private List<List<Integer>> res = new ArrayList<>();
    private boolean[] used;       //判断是否使用过
    // p中保存了一个有index-1个元素的排列。
    // 向这个排列的末尾添加第index个元素, 获得一个有index个元素的排列
    private void generatePermutation(int[] nums,int index,LinkedList<Integer> p){
        //如果包含了所有的元素 则将结果加入res
        if(index == nums.length){
            res.add((LinkedList<Integer>)p.clone());
            return;
        }
        //遍历数组 找到需要添加的index元素
        for(int i=0;i<nums.length;i++){
            if(!used[i]){             //如果没有使用过
                p.addLast(nums[i]);   //加入队尾
                used[i]=true;         //设定使用
                generatePermutation(nums,index+1,p);  //递归调用 index+1
                p.removeLast();       //回溯之后将之前的元素出队
                used[i]=false;        //设定没有访问过
            }
        }
    }
     public List<List<Integer>> permute(int[] nums) {
        if(nums.length==0)
            return res;
        used = new boolean[nums.length];
        //从index0开始
        generatePermutation(nums,0,new LinkedList<>());
        return res;
    }
}