1、解题思路

  1. 回溯法： 使用回溯法生成所有可能的排列。通过交换元素的位置来生成不同的排列。使用标记数组 visited 来记录哪些元素已经被使用过，避免重复使用。时间复杂度：O(n!)，空间复杂度：O(n!)（存储结果的空间）。
  2. 递归法： 递归地生成所有可能的排列。每次选择一个未被使用的元素，将其加入当前排列，然后继续递归。使用标记数组 visited 来记录哪些元素已经被使用过。时间复杂度：O(n!)，空间复杂度：O(n!)（存储结果的空间）。
  3. 库函数法： 使用语言内置的库函数（如 Python 的 itertools.permutations）直接生成所有排列。简单但不符合面试要求。

2、代码实现

C++
#include <vector>
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param num int整型vector
     * @return int整型vector<vector<>>
     */
    vector<vector<int> > permute(vector<int>& num) {
        // write code here
        vector<vector<int>> result;
        backtrack(num, 0, result);
        return result;
    }

    void backtrack(vector<int>& num, int start, vector<vector<int>>& result) {
        if (start == num.size()) {
            result.push_back(num);
            return ;
        }
        for (int i = start; i < num.size(); ++i) {
            swap(num[start], num[i]);
            backtrack(num, start + 1, result);
            swap(num[start], num[i]);
        }
    }
};
Java
import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param num int整型一维数组
     * @return int整型ArrayList<ArrayList<>>
     */
    public ArrayList<ArrayList<Integer>> permute (int[] num) {
        // write code here
        ArrayList<ArrayList<Integer>> result = new ArrayList<>();
        backtrack(num, 0, result);
        return result;
    }

    private void backtrack(int[] nums, int start, ArrayList<ArrayList<Integer>> result) {
        if (start == nums.length) {
            ArrayList<Integer> temp = new ArrayList<>();
            for (int num : nums) {
                temp.add(num);
            }
            result.add(temp);
            return;
        }
        for (int i = start; i < nums.length; ++i) {
            swap(nums, start, i);
            backtrack(nums, start + 1, result);
            swap(nums, start, i);
        }
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}
Python
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param num int整型一维数组 
# @return int整型二维数组
#
class Solution:
    def permute(self , num: List[int]) -> List[List[int]]:
        # write code here
        result = []
        self.backtrack(num, 0, result)
        return result

    def backtrack(self, num, start, result):
        if start == len(num):
            result.append(num[:])
            return
        for i in range(start, len(num)):
            num[start], num[i] = num[i], num[start]
            self.backtrack(num, start + 1, result)
            num[start], num[i] = num[i], num[start]

3、复杂度分析

  1. 回溯法：通过交换元素的位置来生成不同的排列。每次递归调用都固定一个元素的位置，然后继续处理剩下的元素。递归终止条件是所有元素都被固定。
  2. 效率：时间复杂度：O(n!)，因为需要生成所有可能的排列。空间复杂度：O(n!)，用于存储所有排列结果。
  3. 边界条件：当数组长度为1时，直接返回该数组。当数组为空时，返回空列表。
  4. 适用性：回溯法是解决排列问题的经典方法，适用于小规模数据。如果数据规模较大，应考虑其他优化方法或限制条件。