LeetCode 46. 全排列（回溯）
LeetCode 46. 全排列（回溯）
Michael阿明
发布于 2021-02-20 11:08:00
发布于 2021-02-20 11:08:00
1. 题目信息
给定一个没有重复数字的序列，返回其所有可能的全排列。
示例:
输入: [1,2,3]
输出:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/permutations 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
2. 解题
类似题目：
2.1 利用hash map解决
- 在hash map中查找不到的元素，将其push进数组
- 递归处理
class Solution {
public:
vector<vector<int>> permute(vector<int>& nums) {
vector<int> row;
vector<vector<int>> ans;
unordered_map<int, int> m;
bt(nums, 0, m, row, ans);
return ans;
}
void bt(vector<int>& nums, int count, unordered_map<int, int> m, vector<int> row, vector<vector<int>>& ans)
{
if(count == nums.size())
{
ans.push_back(row);
return;
}
for(int i = 0; i < nums.size(); ++i)
{
if(m.find(i) == m.end())
{
m[i] = 1;
row.push_back(nums[i]);
bt(nums,count+1,m,row,ans);
row.pop_back();
m.erase(i);
}
}
}
};2.2 改用bool数组判断是否出现过
用bool数组做判断，节省内存
class Solution {
public:
vector<vector<int>> permute(vector<int>& nums) {
vector<int> row;
vector<vector<int>> ans;
bool occurred[nums.size()];
memset(occurred, 0, sizeof(bool)*nums.size());
bt(nums, 0, occurred, row, ans);
return ans;
}
void bt(vector<int>& nums, int count, bool *occurred, vector<int> row, vector<vector<int>>& ans)
{
if(count == nums.size())
{
ans.push_back(row);
return;
}
for(int i = 0; i < nums.size(); ++i)
{
if(occurred[i] == false)
{
occurred[i] = true;
row.push_back(nums[i]);
bt(nums,count+1,occurred,row,ans);
row.pop_back();
occurred[i] = false;
}
}
}
};本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2019/08/27 ，如有侵权请联系 cloudcommunity@tencent.com 删除
目录
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号