核心思想：回溯算法
回溯類(lèi)似于窮舉枢贿，會(huì)調(diào)用遞歸。當(dāng)遇到要窮舉一些結(jié)果的題目的時(shí)候超凳，可以使用回溯，回溯比窮舉好的地方在于聪建，它可以做剪枝。是深度優(yōu)先搜索（dfs）的一種
void dfs() {
if(邊界條件){
保存結(jié)果;
return;
}
for (int i = 0 ; i<n ; i++){
if (剪枝條件) {
continue;
}
修改全局變量;
if (子狀態(tài)滿(mǎn)足條件) {
dfs (子狀態(tài))
}
恢復(fù)全局變量;
}
}
輸入一個(gè)不含重復(fù)元素的數(shù)組擎析，返回這個(gè)數(shù)組中元素的所有全排列結(jié)果
圖片 1.png
vector<vector<int>> permute (vector<int>& nums) {
vector<vector<int>> res;
visited = vector<bool>(nums.size(), false);
vector<int> p;
dfs(nums, 0, p);
return res;
}
void dfs (vector<int>& nums, int index, vector<int>& p) {
if (index == nums.size()) {
res.push_back(p); // 保存結(jié)果
return;
}
for (int i = 0; i < nums.size() ; i++) {
// 不重復(fù)
if (visited[i] == true) continue;
// 修改全局變量
visited[i] = true;
p.push_back(nums[i]);
// 子狀態(tài)
dfs (nums, index+1, p);
// 恢復(fù)全局變量
visited[i] = false;
q.pop_back();
}
return;
}
數(shù)組中有重復(fù)元素揍魂，輸出全排列
vector<vector<int>> permute (vector<int>& nums) {
vector<vector<int>> res;
visited = vector<bool>(nums.size(), false);
vector<int> p;
sort(nums.begin(), nums.end());// 排序
dfs(nums, 0, p);
return res;
}
void dfs (vector<int>& nums, int index, vector<int>& p) {
if (index == nums.size()) {
res.push_back(p); // 保存結(jié)果
return;
}
for (int i = 0; i < nums.size() ; i++) {
// 不重復(fù)
if (i>0 && nums[i-1] == nums[i] && visited[i-1] == false) continue;//同層去重
if (visited[i] == true) continue;
// 修改全局變量
visited[i] = true;
p.push_back(nums[i]);
// 子狀態(tài)
dfs (nums, index+1, p);
// 恢復(fù)全局變量
visited[i] = false;
q.pop_back();
}
return;
}
