回溯 78.子集 200. 岛屿数量-526互联

回溯算法

为什么
- for循环嵌套很难解决
- 解决问题当问题需要 "回头"，以此来查找出所有的解的时候
  - 排列组合
  - 切割(切割字符串)
  - 子集把子集列出来
  - 棋盘 N皇后/解数独
是什么
- 只要有递归, 就有回溯
- 也是一种纯暴力搜索算法
- 可以抽象成一个树形结构
- 递归函数没有返回值(backtrading)
怎么样
- 最好抽象成一个图形结构
- 处理的框架
```
void backtracking()
{
  if(终止条件)
  {
    收集结果
    return
  }
  for(集合元素)
  {
    处理节点
    递归函数
    回溯操作
  }
}
```
- 看到一个: 作者：show-me-the-code-2
  ①画出递归树，找到状态变量(回溯函数的参数)，这一步非常重要※
  ②根据题意，确立结束条件
  ③找准选择列表(与函数参数相关),与第一步紧密关联※
  ④判断是否需要剪枝
  ⑤作出选择，递归调用，进入下一层
  ⑥撤销选择

class Solution {
public:
    vector<vector<int>> result{};
    vector<int> path{};
    void back_tracking(vector<int> nums,vector<int>& path,int start)
    {
        //肯定有个空集
        result.push_back(path);
        //for循环进行选择
        for(int i = start;i<nums.size();i++)
        { 
            //剪枝 去重(本题没有要求)
            //if(i>start&&nums[i] == nums[i-1]) continue;
            //选择, 加入集合
            path.push_back(nums[i]);
            //递归(向下层) 例: nums= 123 -->1 12 123 13 选择到3,递归就结束
            back_tracking(nums,path,i+1);
            //回溯 撤销选择
            path.pop_back();
        } 
    }
    vector<vector<int>> subsets(vector<int>& nums) {
        back_tracking(nums,path,0);
        return result;
    }
};

200. 岛屿数量

class Solution {
public:
    int result = 0;
    //判断坐标是否在网格中 第r行 第c列
    bool is_in_net(vector<vector<char>>& grid,int r,int c)
    {
        return (0<=r&&r<grid.size())&&(0<=c&&c<grid[0].size());
    }

    //搜索一片陆地
    void dfs(vector<vector<char>>& grid,int r,int c)
    {
        //碰壁返回
        if(!is_in_net(grid,r,c)) return;
        //遇到 水 或者 标记过的 返回
        if(grid[r][c] == '0'||grid[r][c] == '2') return;
        //是陆地, 给个标记
        grid[r][c] = '2';
        //dfs
        dfs(grid,r+1,c);
        dfs(grid,r-1,c);
        dfs(grid,r,c+1);
        dfs(grid,r,c-1);  
    }
    int numIslands(vector<vector<char>>& grid) {
        //陆地为1, 遍历过的陆地为2, 水为0
        //遍历网格
        for(int i = 0;i<grid.size();i++)
        {
            for(int j = 0;j<grid[0].size();j++)
            {
                //找到新陆地
                if(grid[i][j] == '1')
                {
                    dfs(grid,i,j);
                    result++;
                }
            }
        }       
        return result;
    }
};