03 全排列问题
# LeetCode刷题笔记 回溯算法
# 46 全排列 (opens new window)
给定一个不含重复数字的数组 nums
,返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
输入:nums = [1,2,3] 输出:[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
解析:
class Solution {
public:
void bt(vector<int>& nums, int level, vector<vector<int>>& ans){
if(level==nums.size()-1){
ans.push_back(nums);
return;
}
for(int i=level;i<nums.size();++i){
swap(nums[i],nums[level]);
bt(nums,level+1,ans);
swap(nums[i],nums[level]);
}
return;
}
vector<vector<int>> permute(vector<int>& nums) {
vector<vector<int>> ans;
bt(nums,0,ans);
return ans;
}
};
# 47 全排列 II (opens new window)
给定一个可包含重复数字的序列 nums
,按任意顺序 返回所有不重复的全排列。
输入:nums = [1,1,2] 输出: [[1,1,2], [1,2,1], [2,1,1]]
解析:
class Solution {
public:
void bt(vector<int>& nums, int level, vector<vector<int>>& ans){
if(level==nums.size()-1){
ans.push_back(nums);
return;
}
for(int i=level;i<nums.size();++i){
sort(nums.begin()+level,nums.end());
if(i>level && nums[i]==nums[i-1]){
continue;
}
swap(nums[i],nums[level]);
bt(nums,level+1,ans);
swap(nums[i],nums[level]);
}
return;
}
vector<vector<int>> permuteUnique(vector<int>& nums) {
vector<vector<int>> ans;
bt(nums,0,ans);
return ans;
}
};
# 剑指 Offer 38 字符串的排列 (opens new window)
输入一个字符串,打印出该字符串中字符的所有排列。
你可以以任意顺序返回这个字符串数组,但里面不能有重复元素。
输入:s = "abc" 输出:["abc","acb","bac","bca","cab","cba"]
解析:
class Solution {
public:
void bt(string s, int level, vector<string>& ans){
if(level == s.length()-1){
ans.push_back(s);
return;
}
unordered_set<char> set;
for(int i=level;i<s.length();++i){
if(set.count(s[i])){
continue;
}
set.insert(s[i]);
swap(s[i],s[level]);
bt(s,level+1,ans);
swap(s[i],s[level]);
}
return;
}
vector<string> permutation(string s) {
vector<string> ans;
bt(s,0,ans);
return ans;
}
};
上次更新: 2023/11/19, 12:55:48