JAVA 牛牛

46. 全排列

  • Apr 25, 2020
  • 0 views
  • 难度：中等
  • 本题涉及算法：深度优先搜索(DFS)
  • 思路：深度优先搜索(DFS)
  • 类似题型：

题目46. 全排列

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

示例:

输入: [1,2,3]
输出:
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

解题思路

DFS 通用解题步骤

  1. 截止条件
  2. 遍历候选节点
  3. 筛选

DFS搜索执行顺序

如下图

dfs

注意点

  1. res.add(new ArrayList<>(list)) 和res.add(list) 这两个的区别，楼主在这里花了很多时间，读者可以复制在自己的编辑器中看看效果
  2. 当直接发回list 结果为 [] [] [] [] [] [] ,因为是list 只是引用，在遍历的过程中还会继续对list操作
  3. 也就是说，当在返回数据类型为引用类型，需要通过new的方式做返回

参考视频

代码

class Solution {

    List<List<Integer>> res = new ArrayList<List<Integer>>();
    public List<List<Integer>> permute(int[] nums) {
        List<Integer> list = new ArrayList<>();
        boolean[] used = new boolean[nums.length];// 添加判断条件
        DFS(nums,list,used);
        return res;
    }

    public List<Integer> DFS(int[] nums,List<Integer> list,boolean[] used) {
        // 1.截止条件
        if(list.size()==nums.length) {
        //    res.add(list); // 这里是重点
            res.add(new ArrayList<>(list)); // 这里是重点
            return list;
        }

        // 2.遍历候选节点
        for (int i=0;i<nums.length;i++) {
            int c = nums[i];
            // 2.1 筛选
            if (used[i]!=true) {
                list.add(c);
                used[i] = true;
                DFS(nums,list,used);
                list.remove(list.size()-1);
                used[i] = false;
            }
        }
        return list;
    }

}
Search