回溯 78.子集 200. 岛屿数量

回溯算法

• 为什么

  • for循环嵌套很难解决
  • 解决问题 当问题需要 "回头"，以此来查找出所有的解的时候
    • 排列组合
    • 切割(切割字符串)
    • 子集 把子集列出来
    • 棋盘 N皇后/解数独

• 是什么

  • 只要有递归, 就有回溯
  • 也是一种纯暴力搜索算法
  • 可以抽象成一个树形结构
  • 递归函数没有返回值(backtrading)

• 怎么样

  • 最好抽象成一个图形结构
  • 处理的框架

    void backtracking()
    {
      if(终止条件)
      {
        收集结果
        return
      }
      for(集合元素)
      {
        处理节点
        递归函数
        回溯操作
      }
    }
    

  • 看到一个: 作者：show-me-the-code-2
    ①画出递归树，找到状态变量(回溯函数的参数)，这一步非常重要※
    ②根据题意，确立结束条件
    ③找准选择列表(与函数参数相关),与第一步紧密关联※
    ④判断是否需要剪枝
    ⑤作出选择，递归调用，进入下一层
    ⑥撤销选择

78. 子集

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;
    }
};