46. 全排列（回溯算法）

46. 全排列

• 题目
• 解题思路
• 代码

题目

给定一个 没有重复 数字的序列，返回其所有可能的全排列。

解题思路

画出决策树

我们只需要套用模板，把叶子结点的值加入res就可以了。

注意： 排列问题每次通过 contains 方法来排除在 track 中已经选择过的数字；

代码

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

        backtrack(nums,track);
    return res;
    }

    public void backtrack(int[] nums,LinkedList<Integer> track){

        if(track.size()==nums.length){//到达了叶子节点
            res.add(new LinkedList(track));
            return ;
        }

        for(int i=0;i<nums.length;i++){
        // 排除在 track 中已经选择过的数字
        if (track.contains(nums[i])){
            continue;
        }
            track.add(nums[i]);
            backtrack(nums,track);
            track.removeLast();
        }

    }
}