22.回溯算法4

递增子序列

这里不能排序，因为数组的顺序是对结果有影响的，所以只能通过used数组来去重

class Solution {
public:vector<int> path;vector<vector<int>> res;void backtracking(vector<int>& nums,int start){if(path.size()>1)res.push_back(path);int used[201]={0};for(int i=start;i<nums.size();i++){if(path.empty()||nums[i]>=path[path.size()-1]){if(used[nums[i]+100])continue;;path.push_back(nums[i]);used[nums[i]+100]=1;backtracking(nums,i+1);path.pop_back();}}}vector<vector<int>> findSubsequences(vector<int>& nums) {backtracking(nums,0);return res;}
};

全排列

class Solution {
public:vector<int> path;vector<vector<int>> res;int* used;int level=0;void backtracking(vector<int>& nums){if(level==nums.size()){res.push_back(path);return;}for(int i=0;i<nums.size();i++){if(used[i])continue;path.push_back(nums[i]);level++;used[i]=1;backtracking(nums);path.pop_back();used[i]=0;level--;}}vector<vector<int>> permute(vector<int>& nums) {used= new int[nums.size()]{0};backtracking(nums);return res;}
};

全排列2

class Solution {
public:vector<int> path;vector<vector<int>> res;int* used;int level=0;void backtracking(vector<int>& nums){if(level==nums.size()){res.push_back(path);return;}int pre=20040503;for(int i=0;i<nums.size();i++){if(used[i])continue;if(nums[i]==pre)continue;path.push_back(nums[i]);level++;used[i]=1;pre=nums[i];backtracking(nums);path.pop_back();used[i]=0;level--;}}vector<vector<int>> permuteUnique(vector<int>& nums) {used= new int[nums.size()]{0};sort(nums.begin(),nums.end());backtracking(nums);return res;}
};

重新安排行程

class Solution {public:unordered_map<string,map<string,int>> targets;vector<string> res; int tiknum;vector<string> backtracking(int stop,string start){if(stop==tiknum)return res;vector<string> tmp;for(auto it:targets[start]){if(it.second){res.push_back(it.first);targets[start][it.first]--;}else continue;tmp=backtracking(stop+1,it.first);if(!tmp.empty())return tmp;res.pop_back();targets[start][it.first]++;}return tmp;}vector<string> findItinerary(vector<vector<string>>& tickets) {for(auto tick:tickets){targets[tick[0]][tick[1]]++;}tiknum=tickets.size();res.push_back("JFK");return backtracking(0,"JFK");}
};

N皇后

class Solution {
public:vector<string> tmp;vector<vector<string>> res;int n;bool isConf(int y,int x){for(int i=1;i<=y;i++){if(tmp[y-i][x]=='Q')return 1;if(x+i<n&&tmp[y-i][x+i]=='Q')return 1;if(x-i>=0&&tmp[y-i][x-i]=='Q')return 1;}return 0;}void backtracking(int k){if(k==n){res.push_back(tmp);}for(int i=0;i<n;i++){if(isConf(k,i))continue;tmp[k][i]='Q';backtracking(k+1);tmp[k][i]='.';}}vector<vector<string>> solveNQueens(int n0) {n=n0;tmp.resize(n);for(int i=0;i<n;i++){tmp[i].resize(n);for(int j=0;j<n;j++){tmp[i][j]='.';}}backtracking(0);return res;    }
};

• 时间复杂度: O(n!)
• 空间复杂度: O(n)

解数独

class Solution {
public:bool isValid(int row, int col, char val,vector<vector<char>>& board) {for (int i = 0; i < 9; i++) { // 判断行里是否重复if (board[row][i] == val) {return false;}}for (int j = 0; j < 9; j++) { // 判断列里是否重复if (board[j][col] == val) {return false;}}int startRow = (row / 3) * 3;int startCol = (col / 3) * 3;for (int i = startRow; i < startRow + 3; i++) { // 判断9方格里是否重复for (int j = startCol; j < startCol + 3; j++) {if (board[i][j] == val ) {return false;}}}return true;
}bool backtracking(int x,int y,vector<vector<char>>& board){int n=board.size();if(x>=n){x=x%n;y++;}while(x<n&&y<n){if(board[y][x]!='.'){x++;if(x>=n){x=x%n;y++;}continue;}for(int i=1;i<10;i++){if(!isValid(y,x,i+'0',board))continue;board[y][x]=i+'0';           if(backtracking(x+1,y,board))return 1;board[y][x]='.';}return 0;}return 1;}void solveSudoku(vector<vector<char>>& board) {backtracking(0,0,board);}
};