后端开发刷题 | 没有重复项数字的全排列

描述

给出一组数字，返回该组数字的所有排列

例如：

[1,2,3]的所有排列如下
[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2], [3,2,1].
（以数字在数组中的位置靠前为优先级，按字典序排列输出。）

数据范围：数字个数 0<n≤6

要求：空间复杂度 O(n!)，时间复杂度 O(n!）

示例1

输入：

[1,2,3]

返回值：

[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

示例2

输入：

[1]

返回值：

[[1]]

思路分析：

经典的回溯算法问题——全排列（Permutations）

• permute 方法：这是类的公共方法，接收一个整数数组 num 作为输入，并返回一个 ArrayList<ArrayList<Integer>> 类型的列表，其中每个内部列表代表 num 数组的一个排列。

  • 初始化一个 ArrayList<ArrayList<Integer>> 类型的 result 列表，用于存储所有排列。
  • 初始化一个 LinkedList<Integer> 类型的 list，用于在回溯过程中构建当前的排列。
  • 调用 backTrack 方法开始回溯过程。

• backTrack 方法：这是一个私有方法，用于递归地生成所有排列。它接收三个参数：

  • num：原始整数数组。

  • list：当前正在构建的排列（以链表形式）。

  • result：用于存储所有排列的列表。

  • 递归终止条件：如果 list 的大小等于 num 的长度，说明已经构建了一个完整的排列，此时将这个排列（通过 new ArrayList<Integer>(list) 转换为不可变列表）添加到 result 中，并返回。

  • 递归过程：遍历 num 数组中的每个元素，如果当前元素已经存在于 list 中，则跳过该元素（避免重复排列）。否则，将该元素添加到 list 中，并递归调用 backTrack 方法继续构建下一个元素。递归返回后，需要撤销上一步的选择（即移除 list 中最后添加的元素），以便尝试其他可能的排列。

代码：

import java.util.*;

public class Solution {
    public ArrayList<ArrayList<Integer>> permute(int[] num) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<>();

        LinkedList<Integer> list = new LinkedList<>();

        backTrack(num, list, result);
        return result;
    }
    private void backTrack(int[] num, LinkedList<Integer> list,
                           ArrayList<ArrayList<Integer>> result) {
        if (list.size() == num.length) {
            result.add(new ArrayList<Integer>(list));
            return;
        }
        for (int i = 0; i < num.length; i++) {
            if (list.contains(num[i])) {
                continue;
            }
            list.add(num[i]);
            backTrack(num, list, result);
            list.removeLast();
        }
    }
}