七、基础算法精讲：回溯

news/2024/7/20 22:32:59 标签: 算法, 深度优先

目录

  • 一、子集型回溯
    • 1.1 电话号码
    • 1.2 子集
    • 1.3 分割回文串
  • 二、组合型与剪枝
    • 2.1 组合
    • 2.2 组合总和 III
    • 2.3 括号生成
  • 三、排列型
    • 3.1 全排列
    • 3.2 N 皇后
    • 3.3 N 皇后 II

一、子集型回溯

1.1 电话号码

Leetcode 17

MAPPING = "", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        n = len(digits)
        if n == 0:
            return []
        ans = []
        path = [''] * n
        def dfs(i: int)->None:
            if i == n:
                ans.append(''.join(path))
                return
            for c in MAPPING[int(digits[i])]:
                path[i] = c
                dfs(i + 1)
        dfs(0)
        return ans

class Solution {
private:
    string MAPPING[10] = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};

public:
    vector<string> letterCombinations(string digits) {
        int n = digits.size();
        if (!n) return {};
        vector<string> ans;
        string path(n, 0);
        function<void(int)> dfs = [&](int i ) {
            if (i == n) {
                ans.emplace_back(path);
                return;
            }
            for (char c: MAPPING[digits[i] - '0']) {
                path[i] = c;
                dfs(i + 1);
            }
        };
        dfs(0);
        return ans;
    }
};
  • 时间复杂度： O ( n 4 n ) O(n4^n) O(n4n)
  • 空间复杂度： O ( n ) O(n) O(n)

1.2 子集

Leetcode 78

解法一：选或者不选

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        ans = []
        path = []
        n = len(nums)
        def dfs(i: int)->None:
            if i == n:
                ans.append(path.copy())
                return
            dfs(i + 1)
            path.append(nums[i])
            dfs(i + 1)
            path.pop()
        dfs(0)
        return ans

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> ans;
        vector<int> path;
        int n = nums.size();
        function<void(int)> dfs=[&](int i) {
            if (i == n) {
                ans.emplace_back(path);
                return;
            }
            // 不选
            dfs(i + 1);  
            
            // 选择
            path.push_back(nums[i]);
            dfs(i + 1); 
            path.pop_back();
        };
        dfs(0);
        return ans;
    }
};

解法二：选择哪个数

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        ans, path = [], []
        n = len(nums)
        def dfs(i: int)->None:
            ans.append(path.copy())
            if i == n:
                return
            for j in range(i, n):
                path.append(nums[j])
                dfs(j + 1)
                path.pop()
        dfs(0)
        return ans

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> ans;
        vector<int> path;
        int n = nums.size();
        function<void(int)> dfs = [&] (int i) {
            ans.emplace_back(path);
            if (i == n) return;
            for (int j = i; j < n; j ++ ) {
                path.push_back(nums[j]);
                dfs(j + 1);
                path.pop_back();
            }
        };
        dfs(0);
        return ans;
    }
};

1.3 分割回文串

Leetcode 131

class Solution:
    def partition(self, s: str) -> List[List[str]]:
        ans, path = [], []
        n = len(s)
        def dfs(i: int) -> None:
            if i == n:
                ans.append(path.copy())
                return
            for j in range(i, n):
                t = s[i : j + 1]
                if t == t[::-1]:
                    path.append(t)
                    dfs(j + 1)
                    path.pop()
        dfs(0)
        return ans

class Solution {
    bool isPalindrome(string &s, int left, int right) {
        while (left < right)
            if (s[left ++ ] != s[right -- ])
                return false;
        return true;
    }

public:
    vector<vector<string>> partition(string s) {
        vector<vector<string>> ans;
        vector<string> path;
        int n = s.length();
        function<void(int)> dfs = [&](int i) {
            if (i == n) {
                ans.emplace_back(path);
                return;
            }
            for (int j = i; j < n; j ++ ) 
                if (isPalindrome(s, i, j)) {
                    path.push_back(s.substr(i, j - i + 1));
                    dfs(j + 1);
                    path.pop_back();
                }
        };
        dfs(0);
        return ans;
    }
};

二、组合型与剪枝

2.1 组合

Leetcode 77

解法一：选或者不选

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        ans, path = [], []
        def dfs(i: int)->None:
            d = k -len(path)
            if d == 0:
                ans.append(path.copy())
                return
            
            # 不选i
            if i > d: dfs(i - 1)
            
			# 选择i
			path.append(i)
            dfs(i - 1)
            path.pop()
        dfs(n)
        return ans

class Solution {
public:
    vector<vector<int>> combine(int n, int k) {
        vector<vector<int>> ans;
        vector<int> path;
        function<void(int)> dfs = [&](int i) {
            int d = k - path.size();
            if (!d) {
                ans.emplace_back(path);
                return;
            }
            if (i > d) dfs(i - 1);
            path.push_back(i);
            dfs(i - 1);
            path.pop_back();
        };
        dfs(n);
        return ans;
    }
};

解法二：枚举下一个数选择哪个

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        ans, path = [], []
        def dfs(i: int)->None:
            d = k - len(path)  # 还有选择d个数
            if d == 0:
                ans.append(path.copy())
                return
            for j in range(i, d - 1, -1):
                path.append(j)
                dfs(j - 1)
                path.pop()
        dfs(n)
        return ans

class Solution {
public:
    vector<vector<int>> combine(int n, int k) {
        vector<vector<int>> ans;
        vector<int> path;
        function<void(int)> dfs = [&](int i) {
            int d = k - path.size();
            if (!d) {
                ans.emplace_back(path);
                return;
            }
            for (int j = i; j >= d; j -- ) {
                path.push_back(j);
                dfs(j - 1);
                path.pop_back();
            }
        };
        dfs(n);
        return ans;
    }
};

2.2 组合总和 III

Leetcode 216

解法一：枚举下一个属选择哪个

class Solution:
    def combinationSum3(self, k: int, n: int) -> List[List[int]]:
        ans, path = [], []
        def dfs(i: int, t: int)->None:
            """
            i 表示枚举到数（1-9）
            t 表示剩余的总和
            """
            d = k - len(path)

            # 剪枝1：剩余总和小于0
            # 剪枝2：等差求和任然小于t
            if t < 0 or t > (i + i - d + 1) * d // 2:
                return

            if d == 0:
                ans.append(path.copy())
                return
            for j in range(i, d - 1, -1):
                path.append(j)
                dfs(j - 1, t - j)
                path.pop()
        dfs(9, n)
        return ans

class Solution {
public:
    vector<vector<int>> combinationSum3(int k, int n) {
        vector<vector<int>> ans;
        vector<int> path;
        function<void(int, int)> dfs = [&](int i, int t) {
            int d = k - path.size();
            if (t < 0 || t > (i + i - d + 1) * d / 2) return;
            if (!d) {
                ans.emplace_back(path);
                return;
            }
            for (int j = i; j >= d; j -- ) {
                path.push_back(j);
                dfs(j - 1, t - j);
                path.pop_back();
            }
        };
        dfs(9, n);
        return ans;
    }
};

解法二：选或者不选

class Solution:
    def combinationSum3(self, k: int, n: int) -> List[List[int]]:
        ans, path = [], []
        def dfs(i: int, t: int)->None:
            d = k - len(path)
            if t < 0 or t > (i + i - d + 1) * d // 2:
                return
            if d == 0:
                ans.append(path.copy())
                return

            if (i > d): 
                dfs(i - 1, t)
            
            path.append(i)
            dfs(i - 1, t - i)
            path.pop()
        dfs(9, n)
        return ans

class Solution {
public:
    vector<vector<int>> combinationSum3(int k, int n) {
        vector<vector<int>> ans;
        vector<int> path;
        function<void(int, int)> dfs = [&] (int i, int t) {
            int d = k - path.size();
            if (t < 0 || t > (i + i - d + 1) * d / 2) return;
            if (!d) {
                ans.emplace_back(path);
                return;
            }
            
            if (i > d) dfs(i - 1, t);

            path.push_back(i);
            dfs(i - 1, t - i);
            path.pop_back();
        };
        dfs(9, n);
        return ans;
    }
};

2.3 括号生成

Leetcode 22

解法一：枚举填左括号还是右括号

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        m = n * 2
        ans = []
        path = [''] * m
        def dfs(i: int, open: int)->None:
            """
            i: 记录当前枚举到的位置
            open: 记录左括号个数
            """
            if i == m:
                ans.append(''.join(path))
                return
            if open < n:  # 还可以填写左括号
                path[i] = '('
                dfs(i + 1, open + 1)
            if i - open < open:  # 如果括号匹配， i-open == open
                path[i] = ')'
                dfs(i + 1, open)
        dfs(0, 0)
        return ans

class Solution {
public:
    vector<string> generateParenthesis(int n) {
        int m = n * 2;
        vector<string> ans;
        string path(m, 0);
        function<void(int, int)> dfs = [&](int i, int open) {
            if (i == m) {
                ans.emplace_back(path);
                return;
            }
            if (open < n) {
                path[i] = '(';
                dfs(i + 1, open + 1);
            }
            if (i - open < open) {
                path[i] = ')';
                dfs(i + 1, open);
            }
        };
        dfs(0, 0);
        return ans;
    }
};

解法二：枚举下一个左括号的位置

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        ans, path = [], []

        # balance = 左括号个数 - 右括号个数
        def dfs(i: int, balance: int)->None:
            if len(path) == n:
                s = [')'] * (n * 2)
                for j in path:
                    s[j] = '('
                ans.append(''.join(s))
                return 
            
            # 可以填写 0 到 balance 个右括号
            for close in range(balance + 1):  # 填 close 个右括号
                path.append(i + close)  # 填 1 个左括号
                dfs(i + close + 1, balance - close + 1)
                path.pop()

        dfs(0, 0)
        return ans

class Solution {
public:
    vector<string> generateParenthesis(int n) {
        vector<string> ans;
        vector<int> path;

        function<void(int, int)> dfs=[&](int i, int balance) {
            if (path.size() == n) {
                string s(n * 2, ')');
                for (int j: path) s[j] = '(';
                ans.emplace_back(s);
                return;
            }

            for (int close = 0; close <= balance; close ++ ) {
                path.push_back(i + close);
                dfs(i + close + 1, balance - close + 1);
                path.pop_back();
            }
        };
        dfs(0, 0);
        return ans;
    }
};

三、排列型

3.1 全排列

Leetcode 46

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        n = len(nums)
        ans, path = [], [0] * n
        on_path = [False] * n  # 判断是否该数是否被使用
        
        def dfs(i: int)->None:
            if i == n:
                ans.append(path.copy())
                return

            for j, on in enumerate(on_path):
                if not on:
                    path[i] = nums[j]
                    on_path[j] = True
                    dfs(i + 1)
                    on_path[j] = False
        
        dfs(0)
        return ans

class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        int n = nums.size();
        vector<vector<int>> ans;
        vector<int> path(n), on_path(n);
        function<void(int)> dfs = [&](int i) {
            if (i == n) {
                ans.emplace_back(path);
                return;
            }
            for (int j = 0; j < n; j ++ ) 
                if (!on_path[j]) {
                    path[i] = nums[j];
                    on_path[j] = true;
                    dfs(i + 1);
                    on_path[j] = false;
                }
        };
        dfs(0);
        return ans;
    }
};

3.2 N 皇后

Leetcode 51

class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        m = n * 2 - 1
        ans = []
        col = [0] * n
        on_path, diag1, diag2 = [False] * n, [False] * m, [False] * m

        def dfs(r: int)->None:
            if r == n:
                ans.append(['.' * c + 'Q' + '.' * (n - 1 - c) for c in col])
                return
            for c, on in enumerate(on_path):
                if not on and not diag1[r + c] and not diag2[r - c]:
                    col[r] = c
                    on_path[c] = diag1[r + c] = diag2[r - c] = True
                    dfs(r + 1)
                    on_path[c] = diag1[r + c] = diag2[r - c] = False

        dfs(0)
        return ans

class Solution {
public:
    vector<vector<string>> solveNQueens(int n) {
        vector<vector<string>> ans;
        vector<int> col(n), on_path(n), diag1(n * 2 - 1), diag2(n * 2 - 1);

        function<void(int)> dfs=[&](int r) {
            if (r == n) {
                vector<string> board(n);
                for (int i = 0; i < n; i ++ ) 
                    board[i] = string(col[i], '.') + 'Q' + string(n - 1 - col[i], '.');
                ans.emplace_back(board);
                return;
            }

            for (int c = 0; c < n; c ++ ) {
                int rc = r - c + n - 1;
                if (!on_path[c] && !diag1[r + c] && !diag2[rc]) {
                    col[r] = c;
                    on_path[c] = diag1[r + c] = diag2[rc] = true;
                    dfs(r + 1);
                    on_path[c] = diag1[r + c] = diag2[rc] = false;
                }
            }
        };
        dfs(0);
        return ans;
    }
};

3.3 N 皇后 II

Leetcode 52

class Solution:
    def totalNQueens(self, n: int) -> int:
        m = n * 2 - 1
        ans = 0
        on_path, diag1, diag2 = [False] * n, [False] * m, [False] * m
        
        def dfs(r: int)->None:
            if r == n:
                nonlocal ans
                ans += 1
                return
            for c, on in enumerate(on_path):
                if not on and not diag1[r + c] and not diag2[r - c]:
                    on_path[c] = diag1[r + c] = diag2[r - c] = True
                    dfs(r + 1)
                    on_path[c] = diag1[r + c] = diag2[r - c] = False

        dfs(0)
        return ans

class Solution {
public:
    int totalNQueens(int n) {
        int ans = 0;
        vector<int> on_path(n), diag1(n * 2 - 1), diag2(n * 2 - 1);
        function<void(int)> dfs=[&] (int r) {
            if (r == n) {
                ans ++ ;
                return;
            }
            for (int c = 0; c < n; c ++ ) {
                int rc = r - c + n - 1;
                if (!on_path[c] && !diag1[r + c] && !diag2[rc]) {
                    on_path[c] = diag1[r + c] = diag2[rc] = true;
                    dfs(r + 1);
                    on_path[c] = diag1[r + c] = diag2[rc] = false;
                }
            }
        };
        dfs(0);
        return ans;
    }
};

http://www.niftyadmin.cn/n/5190920.html

相关文章

怎么使用Cpolar+Lychee搭建私人图床网站并实现公网访问？

怎么使用Cpolar+Lychee搭建私人图床网站并实现公网访问？

文章目录 1.前言2. Lychee网站搭建2.1. Lychee下载和安装2.2 Lychee网页测试2.3 cpolar的安装和注册 3.本地网页发布3.1 Cpolar云端设置3.2 Cpolar本地设置 4.公网访问测试5.结语 1.前言 图床作为图片集中存放的服务网站&#xff0c;可以看做是云存储的一部分&#xff0c;既可…
阅读更多...
Unity 场景烘培 ——LensFlare镜头光晕（三）

Unity 场景烘培 ——LensFlare镜头光晕（三）

提示&#xff1a;文章有错误的地方&#xff0c;还望诸位大神指出&#xff01; 文章目录 前言一、镜头光晕 (Lens Flares)是什么&#xff1f;二、使用Lens Flares组件总结 前言 一般情况下都会忽略的东西&#xff0c;镜头光晕。理论上不加镜头光晕&#xff0c;也不会有什么影响…
阅读更多...
Pandas+Matplotlib 数据分析

Pandas+Matplotlib 数据分析

利用可视化探索图表 一、数据可视化与探索图 数据可视化是指用图形或表格的方式来呈现数据。图表能够清楚地呈现数据性质&#xff0c; 以及数据间或属性间的关系&#xff0c;可以轻易地让人看图释义。用户通过探索图&#xff08;Exploratory Graph&#xff09;可以了解数据的…
阅读更多...
〖大前端 - 基础入门三大核心之JS篇㊱〗- JavaScript 的DOM节点操作

〖大前端 - 基础入门三大核心之JS篇㊱〗- JavaScript 的DOM节点操作

说明&#xff1a;该文属于 大前端全栈架构白宝书专栏&#xff0c;目前阶段免费&#xff0c;如需要项目实战或者是体系化资源&#xff0c;文末名片加V&#xff01;作者&#xff1a;不渴望力量的哈士奇(哈哥)&#xff0c;十余年工作经验, 从事过全栈研发、产品经理等工作&#xf…
阅读更多...
web前端页面基础

web前端页面基础

web具备三要素&#xff1a; 1、浏览器&#xff1a;通过浏览器访问html页面&#xff0c;发送请求提交到web服务器&#xff0c;并接收和展示服务器返回的html内容 2、web服务器&#xff1a;接收访问浏览器的请求&#xff0c;并将结果发送给浏览器 3、http协议&#xff1a;浏览…
阅读更多...
Cascade-MVSNet论文笔记

Cascade-MVSNet论文笔记

Cascade-MVSNet论文笔记 摘要1 立体匹配&#xff08;Stereo Matching&#xff09;2 多视图立体视觉&#xff08;Multi-View Stereo&#xff09;3 立体视觉和立体视觉的高分辨率输出4 代价体表达方式&#xff08;Cost volume Formulation&#xff09;4.1 多视图立体视觉的3D代价…
阅读更多...
PostgreSQL按月计算每天值的累加

PostgreSQL按月计算每天值的累加

要按月计算每天值的累加&#xff0c;您可以使用PostgreSQL中的日期函数和窗口函数。下面是一个示例查询&#xff0c;假设您有一个名为"table_name"的表&#xff0c;其中包含一个日期列"date_column"和一个数值列"value_column"&#xff1a; SELE…
阅读更多...
Linux上使用Python源码编译安装Python

Linux上使用Python源码编译安装Python

安装python apt install python3-dev python3 python3-venv yum install python38-devel源码安装Python 1.下载需要的Python版本 Python源码地址&#xff1a;https://www.python.org/downloads/source/ 2.安装gcc&#xff08;yum install gcc&#xff09; 3.解压&#xff0c…
阅读更多...
最新文章

Copyright @ 2022~2023