46. 全排列

难度：🟡 Medium | 标签：回溯 | 状态：⬜ LeetCode 链接

思路

回溯：used[i] 标记是否已选。 路径长度等于 n 时收集结果。

代码

class Solution {
    vector<vector<int>> res;
    vector<int> path;
    vector<bool> used;
    void dfs(vector<int>& nums) {
        if (path.size() == nums.size()) { res.push_back(path); return; }
        for (int i = 0; i < (int)nums.size(); ++i) {
            if (used[i]) continue;
            used[i] = true;
            path.push_back(nums[i]);
            dfs(nums);
            path.pop_back();
            used[i] = false;
        }
    }
public:
    vector<vector<int>> permute(vector<int>& nums) {
        used.assign(nums.size(), false);
        dfs(nums);
        return res;
    }
};

复杂度

• 时间 O(n · n!)，空间 O(n)（不计输出）

易错 / 回顾

• 排列 = used[]；组合 = start 索引
• 含重复元素的全排列（47）：先排序 + 「同层去重」if (i > 0 && nums[i] == nums[i-1] && !used[i-1]) continue;