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] = c
                dfs(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] * n
        def dfs(i, nums):
            if i == n:
                res.append(path[:])
                return
            for c in nums:
                path[i] = c
                dfs(i+1, nums-{c})
            return res
        return dfs(0, set(nums))

2. 子集

3. 电话号码的字母组合

4. 组合总和

5. 括号生成

6. 单词搜索

7. 分割回文串

8. N 皇后