全排列
#1、描述46
给定一个 没有重复 数字的序列,返回其所有可能的全排列。
示例:
输入: [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、思路
1、交换 排列组合
2、回溯、深度优先
#3、notes
1、java种的contains函数,C++种find没找到怎么用,就换了一个<bool>的vector
回溯算法:3个问题?
1、路径:也就是已经做出的选择。(track 在累加路径)
2、选择列表:也就是你当前可以做的选择。 (在剩下的nums中寻找)
3、结束条件:也就是到达决策树底层,无法再做选择的条件。
其核心就是 for 循环里面的递归,在递归调用之前「做选择」,在递归调用之后「撤销选择」
参考解析:https://leetcode-cn.com/problems/permutations/solution/hui-su-suan-fa-xiang-jie-by-labuladong-2/
#4、复杂度
时间:O(n*n!)
空间:O(n)
#5、code
class Solution {
private:
vector<vector<int>> res; // 最后答案
public:
vector<vector<int>> permute(vector<int>& nums) { // 主函数调用
vector<bool>flag(nums.size(),true); // 作为访问过与否的标志位
vector<int> track; // 剩余可选择列表
backtrack(nums, track,flag); // d调用递归函数
return res;
}
void backtrack(vector<int>& nums,vector<int>& track,vector<bool>&flag)
{
//触底返回
if(track.size()==nums.size())
{
res.emplace_back(track); // 一个解
return;
}
//
for(int i=0;i<nums.size();i++)
{
if(flag[i]) // 没被访问过,才从此处往下去
{
track.push_back(nums[i]); // 做选择
flag[i]=false;
//进入下一层
backtrack(nums,track,flag);
//撤销动作
//track.erase(track.end()-1);
track.pop_back();
flag[i]=true;
}
}
}
};