LeetCode Hot100 刷题笔记（5）—— 回溯

目录

前言

一、回溯模版

1. 排列型回溯

2. 子集型回溯

3. 组合型回溯

二、回溯例题

1. 全排列

2. 子集

3. 电话号码的字母组合

4. 组合总和

5. 括号生成

6. 单词搜索

7. 分割回文串

8. N 皇后

---

前言

一、回溯模版：排列型回溯，子集型回溯，组合型回溯。

二、回溯例题：全排列，子集，电话号码的字母组合，组合总和，括号生成，单词搜索，分割回文串，N 皇后。(日更中......)

---

一、回溯模版

1. 排列型回溯

例题：章节二_1. 全排列，......

class Solution:def HanShu(self, nums):res = []n = len(nums)path = [0] * n   # [0]中数值0可变def dfs(i):if i == n:res.append(path[:])return for c in nums:path[i] = cdfs(i+1)dfs(0)return res

2. 子集型回溯

例题：......

class Solution:def HanShu(self, nums):res = []n = len(nums)path = [] def dfs(i):res.append(path[:])if i == n:# res.append(path[:])return for j in range(i, n):     ###path.append(num[j])  ###dfs(j+1)       ###path.pop()     ###dfs(0)return res

3. 组合型回溯

二、回溯例题

1. 全排列

原题链接：46. 全排列 - 力扣（LeetCode）

class Solution(object):def permute(self, nums):# 方法(1)：通过 itertools.permutations 实现# from itertools import permutations# return list(permutations(nums))# 方法(2)：回溯res = []n = len(nums)path = [0] * ndef dfs(i, nums):if i == n:res.append(path[:])returnfor c in nums:path[i] = cdfs(i+1, nums-{c})return resreturn dfs(0, set(nums))

2. 子集

3. 电话号码的字母组合

4. 组合总和

5. 括号生成

6. 单词搜索

7. 分割回文串

8. N 皇后