LC46 - 全排列， 以及类似的dfs+回溯问题分析

好几次笔试面试碰到全排列问题了，这回来把它彻底吃透。

[1, 2, 3]这个序列我们要找到他的所有排列方式，那么先用树的形式把它表示出来：

这就是上述问题的决策树了，从根结点到每一个叶子结点就是一种排列方式，我们要做的就是把这颗决策树用代码表示出来。

那么这里用到的方法就是dfs+回溯法，有一个通用的模版：

直接套用模版得到dfs的方法即可，以下是代码：

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        if(nums == null || nums.length == 0) return ans;
        dfs(nums, ans, new ArrayList());
        return ans;
    }

     public static void dfs(int[] nums, List<List<Integer>> result, List<Integer> curList){
        //满足条件，将当前list添加进结果中
        if(curList.size() == nums.length){
            result.add(new ArrayList(curList));
            return;
        }
        List<Integer> tmp = curList;
        for(int i=0 ; i<nums.length; i++){
            //做选择
            if(tmp.contains(nums[i])) continue;
            tmp.add(nums[i]);
            dfs(nums, result, tmp);
            //撤销选择
            curList.remove(curList.size() - 1);
        }
    }
}