在面试中，关于数组的全排列问题是一个经典的考察题目，能够检验候选人的递归思维、回溯算法的理解和实现能力。

思路：

要获取一个数组的全排列，我们可以利用回溯算法。具体来说，回溯算法通过递归的方式逐步生成排列，在每一步都将一个元素加入排列中，然后在下一步递归中排除已选元素，回溯的时候撤销选择，尝试其他可能。

步骤：

1. 递归生成排列：
   • 使用一个辅助数组来记录当前的排列。
   • 对于每个位置，我们尝试填充每一个可能的元素，并递归地填充后续的位置。
   • 使用回溯的方式，在完成一个排列后，撤回当前选择，继续尝试其他可能性。
2. 交换元素：
   • 通过交换数组中的元素来生成排列，而不是额外使用空间存储状态。这样可以减少空间复杂度。

时间复杂度：

• 生成全排列的时间复杂度是 O(n!)，因为每个元素都需要和其他元素交换一遍，排列的总数为 n!。

空间复杂度：

• 空间复杂度是 O(n)，因为递归调用栈的深度是 n（每次递归深度为数组的长度），且我们只需要常数空间来交换数组元素。

Java 代码实现：

import java.util.ArrayList;
import java.util.List;

public class Permutations {

    // 主函数，返回所有的全排列
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        backtrack(nums, new ArrayList<>(), result, new boolean[nums.length]);
        return result;
    }

    // 回溯函数，生成排列
    private void backtrack(int[] nums, List<Integer> current, List<List<Integer>> result, boolean[] used) {
        // 当当前排列的长度等于nums的长度时，说明找到了一个全排列
        if (current.size() == nums.length) {
            result.add(new ArrayList<>(current));
            return;
        }

        // 遍历nums数组中的每个元素
        for (int i = 0; i < nums.length; i++) {
            // 如果该元素已经被使用过，则跳过
            if (used[i]) continue;

            // 做选择，标记当前元素为已使用
            used[i] = true;
            current.add(nums[i]);

            // 递归生成剩余的排列
            backtrack(nums, current, result, used);

            // 撤销选择，回溯
            used[i] = false;
            current.remove(current.size() - 1);
        }
    }

    // 测试主函数
    public static void main(String[] args) {
        Permutations solution = new Permutations();
        int[] nums = {1, 2, 3};
        List<List<Integer>> result = solution.permute(nums);

        // 打印结果
        for (List<Integer> perm : result) {
            System.out.println(perm);
        }
    }
}

代码解析：

1. 主函数 permute(int[] nums)：
   • 该函数会返回所有的全排列。我们初始化一个空的 result 列表，并调用 backtrack 函数来生成排列。
2. 回溯函数 backtrack(int[] nums, List<Integer> current, List<List<Integer>> result, boolean[] used)：
   • current 存储当前的排列结果。
   • used 数组记录每个元素是否已经被选择过。
   • 每次递归，我们将一个没有被使用的元素添加到 current 中，并在递归完成后回溯，撤销当前选择。
3. 时间复杂度和空间复杂度：
   • 时间复杂度：O(n!)，因为要生成n个元素的所有排列，总共有n!个排列，每个排列需要O(n)的时间来生成。
   • 空间复杂度：O(n)，递归调用栈深度最大为n。

测试示例：

对于输入 nums = [1, 2, 3]，输出应为：

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