LeetCode——全排列

NO.46 全排列中等

思路一：深度优先遍历，回溯法 看到全排列，就想到DFS构建树。重点是每条分支路径上每个数组元素只能使用一次。可以使用一个nums.length长度的boolean类型的数组标志每个元素的使用情况，false未使用，true已使用。

递归前先检查当前元素是否被使用过，如果使用过就剪枝；如果未使用过就将当前元素加入集合并将对应的标志设置为true。

每次回溯的时候不仅要将最后加入集合的元素移除，还要将被移除元素对应的标志置为false。

List<List<Integer>> res=new ArrayList<>();
int[] nums;
public List<List<Integer>> permute(int[] nums) {
    if (nums==null||nums.length==0)return res;
    this.nums=nums;
    //标记每个元素是否被使用过，默认值false表示未使用
    boolean[] flag=new boolean[nums.length];
    dfs(new LinkedList<Integer>(),flag);
    return res;
}
//深度优先遍历
private void dfs(LinkedList<Integer> combination,boolean[] flag) {
    //完成组合
    if (combination.size()==nums.length){
        res.add(new ArrayList<>(combination));
        return;
    }
    for (int i=0;i<nums.length;i++){
        //当前元素未使用过，防止一条路径上出现一个元素被重复使用
        if (!flag[i]){
            //将当前元素加入组合中，并将元素对应的标志置为true
            combination.add(nums[i]);
            flag[i]=!flag[i];
            dfs(combination,flag);
            //每次回溯将最后加入的元素移除，并将被移除元素对应的标志置为false
            flag[i]=!flag[i];
            combination.removeLast();
        }
    }
}

时间复杂度：O(N*N!)

本人菜鸟，有错误请告知，感激不尽！

更多题解和学习记录博客:博客、github

NO.46 全排列 中等

NO.46 全排列中等