46. 全排列
3 min
题目
解法：回溯法
思路
核心思想是使用回溯算法通过深度优先搜索枚举所有排列。通过 used 数组标记已使用元素，确保每个元素在一条路径中仅出现一次，当路径长度等于数组长度时得到一个完整排列。
该方法正确性基于穷举思想：每个位置的选择相互独立且无重复，递归过程保证了对 n 个元素的每一种排列组合都恰好生成一次。used 数组维护了元素使用的不变性，path 记录当前路径状态，回溯操作确保状态能正确恢复到上一步以探索其他分支。
- Step 1: 初始化 used 数组标记元素使用状态，path 存储当前排列，ans 存储所有结果
- Step 2: 定义 DFS 函数，当 path 长度等于 nums 长度时，将 path 加入 ans 并返回
- Step 3: 遍历 nums 中每个元素，若未使用则标记为已使用，加入 path，递归调用 DFS
- Step 4: 递归返回后，执行回溯操作：从 path 移除最后元素，并将 used 标记恢复为 false
复杂度
- 时间复杂度:
- 空间复杂度:
代码
class Solution {
public:
vector<vector<int>> permute(vector<int>& nums) {
vector<vector<int>> ans;
vector<int> path;
vector<bool> used(nums.size(), false);
dfs(nums, path, used, ans);
return ans;
}
void dfs(const vector<int>& nums, vector<int>& path, vector<bool>& used, vector<vector<int>>& ans) {
if (path.size() == nums.size()) {
ans.push_back(path);
return;
}
for (int i = 0; i < nums.size(); i++) {
if (!used[i]) {
used[i] = true;
path.push_back(nums[i]);
dfs(nums, path, used, ans);
path.pop_back();
used[i] = false; // 回溯
}
}
class Solution {
public:
vector<vector<int>> permute(vector<int>& nums) {
vector<vector<int>> ans;
vector<int> path;
vector<bool> used(nums.size(), false);
dfs(nums, path, used, ans);
return ans;
}
void dfs(const vector<int>& nums, vector<int>& path, vector<bool>& used, vector<vector<int>>& ans) {
if (path.size() == nums.size()) {
ans.push_back(path);
return;
}
for (int i = 0; i < nums.size(); i++) {
if (!used[i]) {
used[i] = true;
path.push_back(nums[i]);
dfs(nums, path, used, ans);
path.pop_back();
used[i] = false; // 回溯
}
}
}
};