全排列问题--经典回溯算法

0x01.问题

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

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

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

0x02.问题分析

• 全排列问题是一个非常经典的回溯类型的问题，能够很好体现回溯算法思想。

我们先来读一下题，提取要点：

• 所谓全排列就是，一个数组中的所有数重新排列组成新的数组，所有可能组成的新数组就构成了全排列。
• 另外，题目有一个很重要的条件，没有重复的数字，所以我们在考虑的时候就不需要去考虑重复引发的特殊情况。

我们先来粗略的思考一下，如果要达到这种效果，大概应该怎么入手：

• 既然需要得到所有的可能数，所以一定要考虑全面，对于全排列得到的新数组，第一个数可能是任何位置的数，第二个，第三个，都应该可能是任何位置的数，所以，我们的想法可以是：抽取任意的一个数作为新数组的第一个数，然后第二个数从剩下的数中抽取，依次类推。

有了第一个大胆的想法后，我们来分析一下，如果需要达到这个目的，具体需要采取什么样的方式去做：

• 第一个数可能是任何位置的一个数，第二个位置也可能是任何位置的数，对于每一个位置，都需要考虑清楚所有的可能，所以，使用递归的方式去实现是最合适的。

递归的思路也有了，接着就要想如何去实现了，我们要思考清楚里面可能存在的所有细节：

• 细节一：如何知道接下来需要加入新数组的是哪个数？

  • 我们肯定需要对新数组中已经使用过的数字进行记录，对于接下来的加入新数组的那个数，只要不是之前已经出现过的数就行了。
  • 我们可以使用一个哈希表存储已经使用过的数字，每次加入新数字的时候先判断一下。
  • 如果不使用标记的方法又如何？假设当前新数组已经填充到第index个数，那么对于这个新数组来说，[0,index-1]的数字已经填充好了，所以这些数字都不能再使用了，假设当前准备填的数字在原数组中的下标是i，那么，如果我们交换一下第i个数和第index个数，就能够保证在填充下一个数，也就是第index+1个数时，将要填的，都是未出现过的数字。

• 细节二：如何保证考虑所有的情况？

  • 这个问题就是经典的回溯思想了，在当前已经填充的数字等于原数组的长度时，直接将这个新数组加入结果数组。
  • 填充完毕，还要继续回溯去考虑下一种情况，这个时候需要保证还原成填充这个数字之前的状态，也就是回溯。

大致的思路已经出来了，接下来就看代码吧。

0x03.解决代码–回溯

class Solution {
    private void back(int indexindex,int n,ArrayList<Integer> temp,List<List<Integer>> result){
        if(index==n){
            result.add(new ArrayList<Integer>(temp));
        }
        for(int i=index;i<n;i++){
            Collections.swap(temp,index,i);
            back(index+1,n,temp,result);
            Collections.swap(temp,index,i);
        }
    }
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> result=new LinkedList();
        ArrayList<Integer> temp=new ArrayList<Integer>();
        for(int num:nums){
            temp.add(num);
        }
        back(0,nums.length,temp,result);
        return result;
    }
}

ATFWUS --Writing By 2020–04-25