题目
给定一个没有重复数字的数字序列, 输出这写数字的全排列组合.
Input: [1, 2, 3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
思路
这种全排列的问题最直接的思路就是递归.
通过对已经排列的数字进行标记, 来进行循环.
void recrution(vector<int> &nums, int &visit, vector<int> &path, vector<vector<int>> &result) {
if (nums.size() == path.size()) {
// 组装成功
result.push_back(path);
return;
}
for (int i = 0;i < nums.size();i++) {
int isWillVisit = (visit ^ (1<<i)) & (1 <<i);
if (isWillVisit) {
path.push_back(nums[i]);
visit |= (1 << i);
recrution(nums, visit, path, result);
visit ^= (1 << i);
path.pop_back();
}
}
}
// 递归
vector<vector<int>> permute(vector<int>& nums) {
vector<vector<int>> result;
vector<bool> visited(nums.size(), 0);
int visit = 0;
vector<int> path;
recrution(nums, visit, path, result);
return result;
}
总结
运用位运算节约标记成本.
