前言
题目: 46. 全排列
文档: 代码随想录——全排列
编程语言: C++
解题状态: 成功解答!
思路
排列问题综合了之前的回溯问题,但没有新的东西,按部就班回溯就好。
代码
class Solution {
private:
vector<vector<int>> res;
vector<int> path;
void backtracking(vector<int>& nums, vector<bool>& used) {
if (path.size() == nums.size()) {
res.push_back(path);
}
for (int i = 0; i < nums.size(); i++) {
if (used[i] == true) {
continue;
}
path.push_back(nums[i]);
used[i] = true;
backtracking(nums, used);
used[i] = false;
path.pop_back();
}
}
public:
vector<vector<int>> permute(vector<int>& nums) {
res.clear();
path.clear();
vector<bool> used(nums.size(), false);
backtracking(nums, used);
return res;
}
};
- 时间复杂度: O ( n ! ) O(n!) O(n!)
- 空间复杂度: O ( n ) O(n) O(n)
本站资源均来自互联网,仅供研究学习,禁止违法使用和商用,产生法律纠纷本站概不负责!如果侵犯了您的权益请与我们联系!
转载请注明出处: 免费源码网-免费的源码资源网站 » LeetCode46 全排列
发表评论 取消回复