VIVO Android面试题及参考答案

请重写算法题：求数组的全排列。

 思路：

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

步骤：

1. 递归生成排列：

   • 使用一个辅助数组来记录当前的排列。
   • 对于每个位置，我们尝试填充每一个可能的元素，并递归地填充后续的位置。
   • 使用回溯的方式，在完成一个排列后，撤回当前选择，继续尝试其他可能性。

2. 交换元素：

   • 通过交换数组中的元素来生成排列，而不是额外使用空间存储状态。这样可以减少空间复杂度。

时间复杂度：

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

空间复杂度：

• 空间复杂度是 O(