LeetCode-全排序（回溯算法）

每日一题

今天写了一道需要用到回溯的题

题目要求

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

示例 1：

输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

示例 2：

输入：nums = [0,1]
输出：[[0,1],[1,0]]

示例 3：

输入：nums = [1]
输出：[[1]]

题目解析

题目中给了一个不含有重复元素的数组，让我们算出有多少个不同的排列方案，并以数组的形式返回。这道题的思路很明显，我们需要遍历整个数组，让数组中的每一个元素都有作为开头的机会。

但是每个元素开头的情况有很多，我们要依次求出每个位置上元素的可能，因此需要用到回溯。

就比如1，2，3这三个数。

当第一个数是1时，第二个数可能是2或者3，我们就要先求出第二个位置是2时的一个排序方案，再回溯到第一个数是1时，将第二个数变为3，探求这种情况下的排序方案。当数组中的数更多时也是一样的，依次判定每个位置上的选择，选择出一种方案后进行回溯，知道求出所有的方案。

代码实现

这里面用到了一个used数组来记录某个方案中的数字是否已经被使用过。

用了一个数组arr来表示每次的方案，并将其放入结果中。

used[i]=true;
arr.add(nums[i]);
dfs(nums,used,result,arr);
used[i]=false;
arr.remove(arr.size()-1);

代码的关键在于这几行，如果当前数没有被使用过则加到arr中，再次进入搜索，在不断的递归中求出一种方案，随后回溯回来，再将刚刚加入的数字删除，准备下次循环中换成另外一个数字。

在递归中，当arr的长度和数组的长度相等时就代表一种方案已经找到，不用继续递归了。

完成代码如下：

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> res =  new ArrayList<>();
        boolean[] used = new boolean[nums.length];
        List<Integer> arr = new ArrayList<>();
        dfs(nums,used,res,arr);
        return res;
    }
    public void dfs(int[] nums ,boolean[] used, List<List<Integer>> result,List<Integer> arr){
        if(arr.size()==nums.length){
            result.add(new ArrayList<>(arr));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if(used[i]){
                continue;
            }
            else {
                used[i]=true;
                arr.add(nums[i]);
                dfs(nums,used,result,arr);
                used[i]=false;
                arr.remove(arr.size()-1);
            }
        }
    }
}