46.全排列

46.全排列

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

思路：
考虑使用 DFS( Depth-first search 深度优先搜索) 来解决此类问题，很多排列组合相关的问题，都可以通过DFS来解决

class Solution {
    
    //排列结果数组
    private List<List<Integer>> list;
    //保留输入数组，方便后期遍历使用
    private int[] nums;
    //记录每一种组合
    private int[] result;
    //记录是否用过
    private boolean[] used;

    public List<List<Integer>> permute(int[] nums) {

        //边界判断
        if(nums == null) return null;
        //初始化排列结果数组
        list = new ArrayList<>();
        //数组长度判断
        if(nums.length == 0) return list;
        //保存
        this.nums = nums;
        //初始化记录数组
        used = new boolean[nums.length];
        //初始化组合数组
        result = new int[nums.length];
        dfs(0);
        return list;

    }
     
     private void dfs(int idx){

         //不能再往下搜索
         if(idx == nums.length) {
             //为什么不直接把result添加进去呢 ？
             //因为result中的数据会被覆盖 所以创建新的数组
             List<Integer> results =  new ArrayList<>();
             for(int val : result) {
                 results.add(val);
             }
             list.add(results);
             return;
         }

        //枚举这一层所有的选择
        for(int i= 0 ;i < nums.length; i++) {
        
            if(used[i]) continue;//用过就跳过这一步
            result[idx] = nums[i];//记录字符
            used[i] = true;//记录用过
            dfs(idx+1);//钻入下一层
            //来到这里就进入下一轮循环 就还原现场
            used[i] = false;
        }
     }

}

优化方案： 直接操作原数组，把每层可以选择的值 通过层数和索引关系避开

class Solution {

    public List<List<Integer>> permute(int[] nums) {

      //0.边界判断 数组为空 就不处理了
      if(nums==null) return null;
      //1.1 定义全排列结果数组
      List<List<Integer>> list = new ArrayList();
      //1.2 数组中没有元素就返回
      if(nums.length==0) return list;
      //2.DFS
      dfs(list,nums,0);
      //3.返回排列结果
      return list;

    }

    //深度优先搜索
    private void dfs(List<List<Integer>> list,int[] nums,int idx) {
       
       //1.到最后一层了
       if(idx==nums.length) {
           List<Integer> result = new ArrayList();
           for(int val : nums) {
               result.add(val);
           }
           list.add(result);
           return;
       }

       //2.枚举每一层的可能，求出满足要求的排列
       for(int i = idx;i<nums.length;i++) {
           //某一层可以交换的索引 ？第一层 1 可以交换的对象有：123 第二层 2 可以交换的对象有：23
           swap(nums,i,idx);
           //下一层 自动回溯
           dfs(list,nums,idx+1);
           //还原现场
           swap(nums,i,idx);
       }

    }

    //交换两个元素的值
    private void swap(int[] nums,int i ,int j) {
        int tmp = nums[I];
        nums[i] = nums[j];
        nums[j] = tmp;
    }

}

执行结果.png