image.png
要點(diǎn)：
回溯法模版
組合問題：使用startIndex, for循環(huán)每層從startIndex開始 標(biāo)識(shí)為skip 重復(fù)的路徑；
排列問題：使用used 數(shù)組記錄使用情況，for循環(huán)每層從0開始，根據(jù)used 標(biāo)識(shí)為skip 選擇
/*
*數(shù)據(jù)結(jié)構(gòu)
*/
void backtracking(vector<int>& nums)
{
if (中止條件）{
保存結(jié)構(gòu)
return;
}
int i;
for(i=0; i<nums.size();i++){
if(used[i]) continue;
used[i]=true;
path.push_back(nums[i]);
backtracking(nums);
path.pop_back();
used[i]=false;
}
}
class Solution {
public:
vector<int > path;
vector<vector<int>> result;
void backtracking(vector<int>& nums, vector<bool>& used)
{
if (path.size() == nums.size()) {
result.push_back(path);
return;
}
for(int i=0; i< nums.size(); i++ ) {
if (used[i]) continue;
used[i] = true;
path.push_back(nums[i]);
backtracking(nums, used);
path.pop_back();
used[i] = false;
}
}
vector<vector<int>> permute(vector<int>& nums) {
vector<bool > used(nums.size(), false);
backtracking(nums, used);
return result;
}
};
