文章來源：http://www.zghlxwxcb.cn/news/detail-839346.html
思路分析：文章來源地址http://www.zghlxwxcb.cn/news/detail-839346.html
- 使用DFS算法進(jìn)行全排列，遞歸地嘗試每個(gè)可能的排列方式。
- 使用
path向量保存當(dāng)前正在生成的排列，當(dāng)其大小達(dá)到輸入數(shù)組的大小時(shí)，將其加入結(jié)果集。 - 使用
numvisited向量標(biāo)記每個(gè)數(shù)字是否已經(jīng)被訪問過，以確保每個(gè)數(shù)字在一個(gè)排列中只使用一次。 - 在遞歸過程中，對(duì)于每個(gè)未訪問的數(shù)字，將其加入排列，標(biāo)記為已訪問，然后遞歸生成下一個(gè)位置的數(shù)字。
- 在遞歸完成后，需要回溯，撤銷對(duì)當(dāng)前數(shù)字的標(biāo)記，同時(shí)將其從排列中移除，以嘗試其他可能的排列。
- 使用額外的
visited向量標(biāo)記每個(gè)數(shù)字是否已經(jīng)在當(dāng)前排列中被訪問過，避免重復(fù)訪問。
class Solution {
vector<vector<int>> result; // 存儲(chǔ)最終的全排列結(jié)果
vector<int> path; // 存儲(chǔ)當(dāng)前正在生成的排列
// 深度優(yōu)先搜索函數(shù)，生成全排列
void dfs(vector<int>& nums, vector<bool> numvisited) {
vector<bool> visited(21, false); // 用于標(biāo)記數(shù)字是否被訪問過
for (int i = 0; i < nums.size(); i++) {
// 如果當(dāng)前數(shù)字已經(jīng)在當(dāng)前排列中使用過，則跳過
if (numvisited[i] == true)
continue;
path.push_back(nums[i]); // 將當(dāng)前數(shù)字加入排列
numvisited[i] = true; // 標(biāo)記當(dāng)前數(shù)字為已訪問
// 如果當(dāng)前排列長(zhǎng)度等于數(shù)組長(zhǎng)度，說明已經(jīng)生成一個(gè)完整的排列，加入結(jié)果集
if (path.size() == nums.size())
result.push_back(path);
// 如果當(dāng)前數(shù)字在當(dāng)前排列中未被訪問過，則遞歸生成下一個(gè)位置的數(shù)字
if (visited[nums[i] + 10] != true) {
visited[nums[i] + 10] = true;
dfs(nums, numvisited);
}
path.pop_back(); // 回溯，將當(dāng)前數(shù)字從排列中移除
numvisited[i] = false; // 回溯，撤銷對(duì)當(dāng)前數(shù)字的標(biāo)記
}
visited.clear(); // 清除標(biāo)記數(shù)組，節(jié)約空間。
}
public:
// 主函數(shù)，用于生成給定數(shù)組的全排列（包含重復(fù)元素）
vector<vector<int>> permuteUnique(vector<int>& nums) {
vector<bool> numvisited(nums.size(), false); // 初始化數(shù)字訪問標(biāo)記數(shù)組
dfs(nums, numvisited); // 調(diào)用深度優(yōu)先搜索函數(shù)生成全排列
return result; // 返回最終結(jié)果
}
};到了這里，關(guān)于力扣--深度優(yōu)先算法/回溯算法47.全排列 Ⅱ的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
