LeetCode46全排列

问题描述

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

示例:

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

思路

这道题可以使用回溯法来做,以图的方式来展示会更加地直观

在这里仅展示了固定1,固定2的场景.

我们现在来说说在这里的回溯法的思想,首先我们知道如果要求一个数的全排列,那么就可以

  1. 首先固定第一个数,比如是1,
  2. 那么后面的两个数就剩下2,3可以选了,然后我们固定2,
  3. 最后一个数只能选择3,那么固定3.

相同的,我们把这个步骤进一步抽象

  1. 使用递归进行回溯
  2. 在每一次回溯中,固定一个数字,然后进行更深一层的递归
  3. 当全部数字固定完后,对现在的结果输出

在实际的实现中,我们要怎么去固定一个数位呢,我们仔细观察一下上图中的遍历方式,我们看到,比如第一位,是从1开始,到2,再到3的,如果第一位是1,那么二三位就是2和3,那么可以知道,其实这样的回溯,我们可以通过交换来实现.

编码

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

    public void permute(int[] nums,int start,List<List<Integer>> result){
        if(start==nums.length-1){
            List<Integer> list = new ArrayList<>();
            for(int i = 0;i<nums.length;i++){
                list.add(nums[i]);
            }
            result.add(list);
            return;
        }else{
            for(int i = start ;i<nums.length;i++){
                swap(nums,i,start);
                permute(nums,start+1,result);
                swap(nums,i,start);
            }
        }
    }

    public void swap(int[] nums,int i,int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×