模板

void dfs()//参数用来表示状态

{

    if(到达终点状态)

    {

        ...//根据题意添加

        return;

    }

    if(越界或者是不合法状态)

        return;

    if(特殊状态)//剪枝

        return ;

    for(扩展方式)

    {

        if(扩展方式所达到状态合法)

        {

            修改操作;//根据题意来添加

            标记；

            dfs（）；

            (还原标记)；

            //是否还原标记根据题意

            //如果加上（还原标记）就是 回溯法

        }

    }

}

46. 全排列

class Solution {

public:

    vector<vector<int>> res;

    vector<int> vis;

    vector<vector<int>> permute(vector<int>& nums) {

        vector<int> path;

        vis.resize(nums.size(), 0);

        dfs(nums, path, 0);

        return res;

    }

    void dfs(vector<int> & nums, vector<int>& path, int len){//参数表示状态

        if(len == nums.size()){//递归出口

            res.push_back(path);return;

        }

        for(int i = 0;i < nums.size(); i++){//扩展方式

            if(vis[i] == 0){//扩展方式合法

                path.push_back(nums[i]);

                vis[i] = 1;

                dfs(nums,path,len + 1);

                vis[i] = 0;

                path.pop_back();

            }

        }

    }

};

47. 全排列 II 排序去重

class Solution {

public:

    vector<vector<int>> res;

    vector<int> vis;

    vector<vector<int>> permuteUnique(vector<int>& nums) {

        sort(nums.begin(),nums.end());

        vis.resize(nums.size(),0);

        vector<int> path;

        dfs(nums,path, 0);

        return res;

    }

    void dfs(vector<int>& nums, vector<int>& path, int depth){

        if(depth == nums.size()){//递归出口

            res.push_back(path);

            return;

        }

        for(int i = 0; i < nums.size(); i++){

            //在同一深度只会遍历第一个相同的数字，不同深度时vis[i-1] = 1

            if(i && nums[i] == nums[i-1] && vis[i-1] == 0) continue;

            if(vis[i] == 0){

                vis[i] = 1;

                path.push_back(nums[i]);

                dfs(nums,path,depth + 1);

                vis[i] = 0;

                path.pop_back();

            }

        }

    }

};

491. 递增子序列

class Solution {

public:

    vector<vector<int>> res;

    vector<int> vis;

    vector<vector<int>> findSubsequences(vector<int>& nums) {

            vis.resize(nums.size(),0);

           vector<int> path;

           dfs(nums,path,0);

           return res;

    }

    void dfs(vector<int> & nums, vector<int>& path, int start){//参数表示状态，从前往后，depth改为start

        if(path.size() >= 2){//过程状态也要记录

                res.push_back(path);

        }

        if(start == nums.size()) return;

        unordered_set<int> mp;//去重

        for(int i = start;i < nums.size(); i++){//扩展方式

            //if(vis[i] == 0){这里不需要vis

            if((path.size() == 0 || nums[i] >= path.back()) && mp.count(nums[i]) == 0){

                mp.insert(nums[i]);

                path.push_back(nums[i]);

                dfs(nums,path,i + 1);//这里别写错了

                path.pop_back();

            }

        }

    }

};

39. 组合总和

元素可以重复利用且没有顺序，所以不要vis数组

class Solution {

public:

    vector<vector<int>> res;

    vector<vector<int>> combinationSum(vector<int>& nums, int target) {

        vector<int> path;

        dfs(nums,path,0,target);

        return res;

    }

    void dfs(vector<int> &nums,vector<int>& path, int start, int target){

            //出口

        if(target < 0) return;

        if(target == 0){

            res.push_back(path);

            return;

        }

        //遍历

        for(int i = start; i <nums.size(); i++){

            path.push_back(nums[i]);

            dfs(nums,path,i, target - nums[i]);

            path.pop_back();

        }

    }

};

40. 组合总和 II 比上题多了一个去重操作；

class Solution {

public:

    vector<vector<int>> res;

    vector<vector<int>> combinationSum2(vector<int>& nums, int target) {

        sort(nums.begin(),nums.end());//加个去重操作

        vector<int> path;

        dfs(nums,path,0,target);

        return res;

    }

    void dfs(vector<int> &nums,vector<int>& path, int start, int target){

            //出口

        if(target < 0) return;

        if(target == 0){

            res.push_back(path);

            return;

        }

        //遍历

        for(int i = start; i <nums.size(); i++){

            if(i > start && nums[i] == nums[i-1] ) continue;//注意是i > start

            path.push_back(nums[i]);

            dfs(nums,path,i+1, target - nums[i]); // start = i + 1

            path.pop_back();

        }

    }

};

78. 子集

class Solution {

public:

    vector<vector<int>> res;

    vector<int> vis;

    vector<vector<int>> subsets(vector<int>& nums) {

            vis.resize(nums.size(),0);

           vector<int> path;

           dfs(nums,path,0);

           return res;

    }

    void dfs(vector<int> & nums, vector<int>& path, int start){//参数表示状态，从前往后，depth改为start

         res.push_back(path);

        if(start == nums.size()) return;

        for(int i = start;i < nums.size(); i++){//扩展方式

                //似乎没条件

                path.push_back(nums[i]);

                dfs(nums,path,i + 1);//这里别写错了

                path.pop_back();

        }

    }

};

90. 子集 II 上题基础上加个去重

class Solution {

public:

    vector<vector<int>> res;

    vector<int> vis;

    vector<vector<int>> subsetsWithDup(vector<int>& nums) {

            sort(nums.begin(), nums.end());//排序便于去重

            vis.resize(nums.size(),0);

           vector<int> path;

           dfs(nums,path,0);

           return res;

    }

    void dfs(vector<int> & nums, vector<int>& path, int start){//参数表示状态，从前往后，depth改为start

         res.push_back(path);

        if(start == nums.size()) return;

        for(int i = start;i < nums.size(); i++){//扩展方式

                if(i > start && nums[i] == nums[i-1]) continue; //去重

                path.push_back(nums[i]);

                dfs(nums,path,i + 1);//这里别写错了

                path.pop_back();

        }

    }

};

进阶：N皇后问题

51. N皇后

class Solution {

public:

    vector<vector<string>> res;

    vector<vector<string>> solveNQueens(int n) {

        string t = "";

        for(int i = 0; i < n; i++) t += '.';

        vector<string> path(n,t);

        vector<vector<int>> vis(n, vector<int>(n,0));

        dfs(path,vis,n,0);

        return res;

    }

    void dfs(vector<string>& path,vector<vector<int>> &vis, int& n, int row){

        if(row == n){//递归出口，前n行全部被赋值

            res.push_back(path);return;

        }

        for(int j = 0; j < n; j++){//遍历一行

            if(vis[row][j] == 0){//条件

                path[row][j] = 'Q';

                //注意，不能直接让vis变1和变0，否则后来的修改可能会改变原来的修改

                for(int i = row; i < n; i++)vis[i][j]++;//该列

                for(int i = row; i < n; i++){//对角线

                    if(j + i - row < n) vis[i][j + i - row]++;

                    if(j + row - i >= 0) vis[i][j + row - i]++;

                }

                dfs(path, vis, n, row + 1);

                path[row][j] = '.';

                for(int i = row; i < n; i++)vis[i][j]--;//该列

                for(int i = row; i < n; i++){//对角线

                    if(j + i - row < n) vis[i][j + i - row]--;

                    if(j + row - i >= 0) vis[i][j + row - i]--;

                }

            }

        }

    }

};

37. 解数独

class Solution {

public:

    int col[9][9] = {0};

    int row[9][9] = {0};

    int box[9][9] = {0};

    void solveSudoku(vector<vector<char>>& board) {

        int n = board.size();

        //初始化

        for(int i = 0; i <9; i++)

            for(int j = 0; j < 9; j++){

                if(board[i][j] != '.'){

                    int t = board[i][j] - '1';

                    col[j][t]++;

                    row[i][t]++;

                    box[i/3*3+ j/3][t]++;

                }

            }

        dfs(board, 0, 0);

    }

    //传参 int a[][9] 或者 int (*a)[9] 而不是 (int*)[9] a

    // box x/3*3 + y/3 而不是 x/3 + y/3;

    // (y + 1)%3 而不是 (++y)/3

    bool dfs(vector<vector<char>>& board,  int x, int y){

        if(x == 9) return true;//递归出口

        //特殊状态

        if(board[x][y] != '.') return dfs(board,x + (y==8),(++y)%9);

        for(int k = 0; k < 9; k++){//遍历

            //条件

            if(row[x][k] || col[y][k] || box[x/3*3 + y/3][k]) continue;

            board[x][y]  = k + '1';

            row[x][k]++;col[y][k]++;box[x/3*3 + y/3][k]++;

            if(dfs(board,x + (y==8),(y + 1)%9)) return true;//找到一个解就退出

            board[x][y]  = '.';

            row[x][k]--;col[y][k]--;box[x/3*3 + y/3][k]--;

        }

        return false;

    }

};

最新文章

  1. dom 节点篇
  2. 面向amd64的XXX与与项目的目标平台“x86”不兼容
  3. C++ STL 的实现：
  4. windows2003批量添加和导出所有ip
  5. Oracle数值处理函数 （绝对值、取整...）
  6. 关于HTTP协议
  7. linux的chmod与chown命令详解
  8. 1N系列稳压二极管参数
  9. JS学习笔记：（二）回流和重绘
  10. NeuChar 平台使用及开发教程 索引
  11. IOS 设置视图半透明子控件不透明
  12. Background removal with deep learning
  13. JS设计模式（10）职责链模式（重要）
  14. 并行编程（Parallel Framework）
  15. selective search
  16. 【liunx】Linux下的压缩和解压缩命令——jar
  17. MQ有啥用
  18. matplotlib.pyplot中add_subplot方法参数111的含义
  19. H5 Js图片转base64编码
  20. C# 指南之装箱与拆箱

热门文章

  1. [cocos2d-x]飞机大战 遇到的bug和总结（二）
  2. 一、tcp三次握手
  3. .NET周报【1月第2期 2023-01-13】
  4. MySQL 如何实现表的创建、复制、修改与删除
  5. 快速入门API Explorer
  6. Redis01 Redis详细介绍
  7. DVWA靶场实战(十四)——JavaScript
  8. 合肥光源纵向震荡数据源相关PV
  9. 郁金香 注入DLL代码 与MFC窗口DLL文件 开源
  10. xmind使用分享