Leecode 90. 子集 II

链接：https://leetcode.cn/problems/subsets-ii/

那么这道题和上一道题有什么区别呢？

没什么区别，就是仅仅多了重复元素而已，那怎么搞？

实际上[1,4,4]和[4,1,4]是同一个子集，所以就还要去重

不急，在递归的下面加上这句话

 while(i+1 < nums.size() && vec[vec.size()-1] == nums[i+1]

在pop元素之前，如果我们发现要pop的元素和下一个push进来的元素一毛一样，那么我们就让i++

class Solution {
public:vector> ans;vector vec;void recursion(vector& nums,int k,int step){// 元素收集满了，记录当前vec然后returnif(vec.size() == k){ans.push_back(vec);return;}for(int i = step;ivec.push_back(nums[i]);recursion(nums,k,i + 1); // 是取搜下一个元素了while(i+1 < nums.size() && vec[vec.size()-1] == nums[i+1]) i++; // 那么就跳过重复的数据呗vec.pop_back();}}vector> subsetsWithDup(vector& nums) {sort(nums.begin(),nums.end());for(int i = 1; i< nums.size() ;i++) {vec.clear();recursion(nums,i,0); }//vector> res (ans.begin(),ans.end());ans.push_back({});ans.push_back(nums);return ans;}
};

Leecode 491. 递增子序列

链接：https://leetcode.cn/problems/increasing-subsequences/description/

注意，这个题目比较特别

因为要求输出递增序列，因此是不可以排序的，而我们之前推崇的办法

while(i + 1 < nums.size() && nums[i+1] == vec[vec.size()-1]) i++;

也仅仅在排好序的数组上管用

所以我们需要重新思考去重的方式——set

同时因为题目要求递增，所以需要在push之前判断当前元素是不是比vector中的最后一个元素大

class Solution {
public:set> ans;vector vec;void recursion(vector& nums,int k,int step){if(vec.size() == k){ans.insert(vec);return;}for(int i=step;iif(!vec.empty() && nums[i] >= vec[vec.size()-1] || vec.empty()) // 如果满足递增，再把元素给push进来{vec.push_back(nums[i]);recursion(nums,k,i + 1);//while(i + 1 < nums.size() && nums[i+1] == vec[vec.size()-1]) i++; // 不能排序这个办法基本上就死了，所以需要setvec.pop_back();}}}vector> findSubsequences(vector& nums) {//sort(nums.begin(),nums.end()); // 注意这个题目是不允许排序的for(int i=2;i<=nums.size();i++){vec.clear();recursion(nums,i,0);}vector> res(ans.begin(),ans.end());return res;}
};

Leecode 46. 全排列

链接：https://leetcode.cn/problems/permutations/

确实是需要used数组了，记录当前哪些元素用过哪些元素没有用过

值得注意的一点是：used中的索引值需要是当前元素在nums中的索引而不能是当前元素的值，因为当前元素可能是负值···

class Solution {
public:// 想返回全排列最好的办法就是用数组记重了vector> res;vector vec;int used[100];void recurison(vector& nums){if(vec.size() == nums.size()) {res.push_back(vec);return;}for(int i = 0;iif(!used[i]) // 最好是记录索引而不是值，因为值有可能是负的{vec.push_back(nums[i]);used[i] = 1;recurison(nums);used[i] = 0;vec.pop_back();}}}vector> permute(vector& nums) {recurison(nums);return res;}
};

Leecode 47. 全排列 II

链接：https://leetcode.cn/problems/permutations-ii/

加个set去重咯，没有新意~

class Solution {
public:set> ans;vector vec;int used[100];void recurison(vector& nums){if(vec.size() == nums.size()) {ans.insert(vec);return;}for(int i = 0;iif(!used[i]) // 最好是记录索引而不是值，因为值有可能是负的{vec.push_back(nums[i]);used[i] = 1;recurison(nums);used[i] = 0;vec.pop_back();}}}vector> permuteUnique(vector& nums) {recurison(nums);vector> res(ans.begin(),ans.end());return res;}
};

Leecode 332. 重新安排行程

链接：https://leetcode.cn/problems/reconstruct-itinerary/

孙哥讲的真很好，很细

class Solution {
unordered_map> targets;bool backtracking(int ticketNum, vector& result) {if (result.size() == ticketNum + 1) {return true;}for (pair& target : targets[result[result.size() - 1]]) {if (target.second > 0 ) { // 记录到达机场是否飞过了result.push_back(target.first);target.second--;if (backtracking(ticketNum, result)) return true;result.pop_back();target.second++;}}return false;}public:vector findItinerary(vector>& tickets) {targets.clear();vector result;for (const vector& vec : tickets) {targets[vec[0]][vec[1]]++; // 记录映射关系}result.push_back("JFK"); // 起始机场backtracking(tickets.size(), result);return result;}
};

Leecode 51. N 皇后

链接：https://leetcode.cn/problems/n-queens/

经典练手题

// 区区n皇后是困难？？？
class Solution {
public:vector> res;// 首先我们枚举行，从左到右，看行上的哪个元素可以放置Qbool check(int n,int row,int column,vector &test){   // [row,column]// 若是在row这行有元素，我们就直接return falsefor(int i=0;i   if(test[i][column] == 'Q') return false;if(row - i >= 0 && column + i if(test[row - i][column + i] == 'Q') return false;}if(row - i >= 0 && column - i >=0) {if(test[row - i][column - i] == 'Q') return false;}}return true;c    }void recursion(int n,int step,vector &test) // 直接修改test数组{// 如果当前枚举的行数已经超过了n，那么我们直接就记录当前答案然后returnif(step > n-1) {res.push_back(test);return;}for(int i=0;iif(check(n,step,i,test)) // 如果当前位置是合法的{test[step][i] = 'Q';recursion(n,step + 1,test);test[step][i] = '.';}}}vector> solveNQueens(int n) // 此处的n给的是棋盘的大小 { // 首先需要初始化数组，答案是用三维数组装填的vector test(n , string(n,'.')); // 刚开始我们将数组全部都用'.'装填之recursion(n,0,test);return res;}
};

Leecode 37. 解数独

经典练手题2，主要看细不细

首先我们考虑如何递归的问题：按理说是9*9的方格逐个位置搜索，那用for循环枚举位置不是有点多余？因为移动挺有规律的，所以我们这里就没有用两层for循环去枚举位置（加上枚举数字就有三层循环了），我们只要枚举当前位置需要填入的值就OK了

至于行数和列数，一般都是递归到当前行的下一列，只有当前行所有列全都遍历完毕才会去下一行，根据这个规律就能得到下一次递归的位置在哪

还有一个需要注意的点：数独数组本来就是有值的，并且我们在填充数独的过程中是不可以改变原来数独中的值的，因此我们在递归的过程中发现当前位置若是有值，就直接递归到下一层。并且，从此处回溯是不合理的，所以在递归操作的后面直接加上return避免此处回溯进入到后面的for循环，同时也提高了效率

除此之外，我设计了一个check函数，用来判断在当前位置填入num是否合法——还是为了提高效率，开始的时候我们就得到了不完全的数独数组，为了避免重复值出现在“同一行”，“同一列”，“同一个3 * 3矩阵”中，我们还要定义三个数组用来记录“当前行”，“当前列”，“当前的3 * 3矩阵中哪些数字被使用过

最后还有一个需要注意的点：数独填充完毕后是要return的，但是真的return回来所有被填充的数字又会变成’.'，所以在填充完毕后，我们定义标志位flag为1，并且在回溯的时候加上判断——只有在标志位不为1的时候才回溯，这样我们return回来的数组就是完整的

class Solution {
public:int rows[10][10];int cols[10][10];int cell[10][10][10];int flag = 0;// 首先先遍历一遍数独，将其中都是1的位置全都置为1，表示这个元素已经被使用过了
bool check(int row, int col, vector>& board, int num)
{// 若是行中列中包括cell中都没有出现过这个元素，那么return trueif (rows[row][num]) return false;if (cols[col][num]) return false;if (cell[row/3][col/3][num]) return false;return true;
}
void recursion(vector>& board, int row, int col)
{if (flag) return;if (col == 9)        { col = 0; row += 1; }if (row == 9 && col == 0) // 已经将数组填充完毕{flag = 1;return;}if (board[row][col]!='.') { recursion(board, row, col + 1); return; } // 如果当前有元素，直接跳过，并且不允许回溯，直接return// 你觉得需要用for循环枚举位置吗，是不是所有顺序都是固定的for (int num = 1; num <= 9; num++) // num是当前准备填充的元素{if (check(row, col, board, num)){board[row][col] = num + '0';rows[row][num] = 1; // 第row行的num已经用过了cols[col][num] = 1; // 第col列的num已经用过了cell[row/3][col/3][num] = 1;recursion(board, row, col + 1);if (flag) return;board[row][col] = '.';rows[row][num] = 0; // 第row行的num没用过cols[col][num] = 0; // 第col列的num没用过cell[row/3][col/3][num] = 0;}}}
void solveSudoku(vector>& board)
{memset(rows, 0, sizeof(rows));memset(cols, 0, sizeof(cols));memset(cell, 0, sizeof(cell));for (int i = 0; i<9; i++)for (int j = 0; j<9; j++){if (board[i][j] != '.'){int num = board[i][j] - '0';rows[i][num] = 1; // 第i行的num已经用过了cols[j][num] = 1; // 第j列的num已经用过了;cell[i/3][j/3][num] = 1;}}recursion(board, 0, 0);
}
};