全排列
每一个树枝都元素都只能出现一次
回溯法
class Solution { public: vector<vector<int>> result; vector<int> path; void backtracking(vector<int> &nums) { if(path.size() == nums.size()) { result.push_back(path); return; } for(int i = 0 ; i<nums.size() ; i++) { auto it = find(path.begin(),path.end(),nums[i]); //如果这个元素在这个树枝之前用过，就跳出 if(it == path.end()) { path.push_back(nums[i]); }else { continue; } backtracking(nums); path.pop_back(); } return; } vector<vector<int>> permute(vector<int>& nums) { backtracking(nums); return result; } };
回溯标记法
class Solution { public: vector<vector<int>> result; vector<int> path; 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] == true) continue; // path里已经收录的元素，直接跳过 used[i] = true; path.push_back(nums[i]); backtracking(nums, used); path.pop_back(); used[i] = false; } } vector<vector<int>> permute(vector<int>& nums) { result.clear(); path.clear(); vector<bool> used(nums.size(), false); backtracking(nums, used); return result; } };
二刷
class Solution { public: vector<vector<int>> result; vector<int> path; vector<bool> underNum; void track_back(vector<int>& nums ) { if(path.size() >= nums.size()) { result.push_back(path); return; } for(int i=0 ; i<nums.size();i++) { if(underNum[i] == true ) continue; underNum[i] = true; path.push_back(nums[i]); track_back(nums); path.pop_back(); underNum[i] = false; } return; } vector<vector<int>> permute(vector<int>& nums) { if(nums.size() == 0 ) return result; underNum.assign(nums.size(),false); track_back(nums); return result; } };
