voidbacktrack(vector<int>& nums){ // base case,到达叶子节点 if (track.size() == nums.size()) { // 收集叶子节点上的值 res.push_back(vector<int>(track.begin(), track.end())); return; } // 回溯算法标准框架 for (int i = 0; i < nums.size(); i++) { // 已经存在 track 中的元素,不能重复选择 if (used[i]) { continue; } // 做选择 used[i] = true; track.push_back(nums[i]); // 进入下一层回溯树 backtrack(nums); // 取消选择 track.pop_back(); used[i] = false; } }
组合问题(元素不重复不可复选)
选择列表:避免选只是顺序不同的相同元素序列
解决方案:通过保证元素之间的相对顺序不变来防止出现重复的子集
代码实现
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
// C(n,k) voidbacktrack(int start, int n, int k){ // base case if (k == track.size()) { // 遍历到了第 k 层,收集当前节点的值 res.push_back(vector<int>(track.begin(), track.end())); return; }
// 回溯算法标准框架 for (int i = start; i <= n; i++) { // 选择 track.push_back(i); // 通过 start 参数控制树枝的遍历,避免产生重复的子集 backtrack(i + 1, n, k); // 撤销选择 track.pop_back(); } }
intnumIslands(vector<vector<char>>& grid){ int res = 0; int m = grid.size(), n = grid[0].size(); // 遍历 grid for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (grid[i][j] == '1') { // 每发现一个岛屿,岛屿数量加一 res++; // 然后使用 DFS 将岛屿淹了 dfs(grid, i, j); } } } return res; }
// 从 (i, j) 开始,将与之相邻的陆地都变成海水 voiddfs(vector<vector<char>>& grid, int i, int j){ int m = grid.size(), n = grid[0].size(); if (i < 0 || j < 0 || i >= m || j >= n) { // 超出索引边界 return; } if (grid[i][j] == '0') { // 已经是海水了 return; } // 将 (i, j) 变成海水 grid[i][j] = '0'; // 淹没上下左右的陆地 dfs(grid, i + 1, j); dfs(grid, i, j + 1); dfs(grid, i - 1, j); dfs(grid, i, j - 1); }