腾讯常用算法测试题：全排列（回溯算法解答）

给定表中没有重复数字的数字，返回所有可能的全排列。您可以按任意顺序返回答案。

例1：

输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

例2：

输入：nums = [0,1]
输出：[[0,1],[1,0]]

这个问题可以通过使用返回算法来解决。完整代码如下：

class Solution {
    //全排列，即所有路径集合
    List<List<Integer>> allPath = new LinkedList<>();

    public List<List<Integer>> permute(int[] nums) {
        //当前路径，入口路径，path是空的
        List<Integer> path =  new LinkedList<>();
        //递归函数入口，可做选择是nums数组
        backTrace(nums,path);
        return allPath;
    }

    public void backTrace(int[] nums,List<Integer> path){
        //已走路径path的数组长度等于nums的长度,表示走到叶子节点，所以加到全排列集合
        if(nums.length==path.size()){
           allPath.add(new LinkedList(path));
           return;
        }

        for(int i=0;i<nums.length;i++){
            //剪枝，排查已经走过的路径
            if(path.contains(nums[i])){
                continue;
            }
            //做选择，加到当前路径
            path.add(nums[i]);
            //递归，进入下一层的决策
            backTrace(nums,path);
            //取消选择
            path.remove(path.size() - 1);
        }
    }
}