分析

• 本题的考点：递归回溯。

• 这个题目使用暴搜搜出所有的方案即可，关键问题是搜索顺序是什么？一般由两种搜索顺序：

（1）可以枚举每个位置放置哪个数据；（最常用）

（2）枚举每个数据放置到哪个位置上。

• 这里使用第（1）中枚举方式。

• 这里使用数据st表示某个某个数据是否已经被使用。

代码

• C++

class Solution {
public:
    vector<vector<int>> ans;
    vector<int> path;  // 每次搜到的方案
    vector<bool> st;  // st[i] == true说明nums[i]已经被使用了

    vector<vector<int>> permute(vector<int>& nums) {

        path = vector<int>(nums.size());
        st = vector<bool>(nums.size());

        dfs(nums, 0);

        return ans;
    }

    // 当前考虑到nums[u]
    void dfs(vector<int> &nums, int u) {
        if (u == nums.size()) {
            ans.push_back(path);
            return;
        }

        for (int i = 0; i < nums.size(); i++)
            if (!st[i]) {
                path[u] = nums[i];
                st[i] = true;
                dfs(nums, u + 1);
                st[i] = false;
            }
    }
};

• Java

class Solution {

    List<List<Integer>> ans = new ArrayList<>();
    int[] path;
    boolean[] st;

    public List<List<Integer>> permute(int[] nums) {

        path = new int[nums.length];
        st = new boolean[nums.length];

        dfs(nums, 0);

        return ans;
    }

    private void dfs(int[] nums, int u) {
        if (u == nums.length) {
            ans.add(Arrays.stream(path).boxed().collect(Collectors.toList()));
            return;
        }

        for (int i = 0; i < nums.length; i++)
            if (!st[i]) {
                path[u] = nums[i];
                st[i] = true;
                dfs(nums, u + 1);
                st[i] = false;
            }
    }
}

时空复杂度分析

• 时间复杂度：$O(n!)$，n为输入数组的长度。

• 空间复杂度：$O(n)$，n为输入数组的长度。这里不考虑存储答案的二维数组，考虑的话空间复杂度为$O(n \times n!)$。