《灵珠觉醒:从零到算法金仙的C++修炼》卷三·天劫试炼(51)混沌钟定排列 - 全排列(回溯与剪枝)
《灵珠觉醒:从零到算法金仙的C++修炼》卷三·天劫试炼(51)混沌钟定排列 - 全排列(回溯与剪枝)
哪吒在数据修仙界中继续他的修炼之旅。这一次,他来到了一片神秘的混沌时钟林,林中有一座古老的混沌钟,钟身闪烁着神秘的光芒。钟的入口处有一块巨大的石碑,上面刻着一行文字:“欲定此钟,需以混沌之力,全排列,回溯剪枝显真身。”
哪吒定睛一看,石碑上还有一行小字:“数组[1, 2, 3]
的全排列为[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
。”哪吒心中一动,他知道这是一道关于全排列的难题,需要通过回溯与剪枝的方法,生成数组的所有排列。
暴力解法:混沌钟的初次尝试
哪吒心想:“要生成全排列,我可以逐个元素交换。”他催动混沌钟之力,通过逐个元素交换,试图生成所有可能的排列。
vector<vector<int>> permute(vector<int>& nums) {
vector<vector<int>> result;
sort(nums.begin(), nums.end());
do {
result.push_back(nums);
} while (