[TOC]

深度优先遍历

定义

「一条路走到底，不撞南墙不回头」。深度优先遍历 只要前面有可以走的路，就会一直向前走，直到无路可走才会回头；

无路可走有两种情况：
① 遇到了墙；
② 遇到了已经走过的路；

在无路可走的时候，沿着原路返回，直到回到了还有未走过的路的路口，尝试继续走没有走过的路径；有一些路径没有走到，这是因为找到了出口，程序就停止了；

树的深度优先遍历

二叉树的深度优先遍历从「根结点」开始，依次 「递归地」 遍历「左子树」的所有结点和「右子树」的所有结点。

二叉树的深度优先遍历还可以分为：前序遍历、中序遍历和后序遍历。

1. 前序遍历
   对于任意一棵子树，先输出根结点，再递归输出左子树的 所有 结点、最后递归输出右子树的 所有 结点。上图前序遍历的结果就是深度优先遍历的结果：[0、1、3、4、7、2、5、8、9、6、10]。

2. 中序遍历
   对于任意一棵子树，先递归输出左子树的 所有 结点，然后输出根结点，最后递归输出右子树的 所有 结点。上图中序遍历的结果是：[3、1、7、4、0、8、5、9、2、10、6]。

3. 后序遍历（重要）
   对于任意一棵子树，总是先递归输出左子树的 所有 结点，然后递归输出右子树的 所有 结点，最后输出根结点。后序遍历体现的思想是：先必需得到左右子树的结果，才能得到当前子树的结果，这一点在解决一些问题的过程中非常有用。上图后序遍历的结果是：[3、7、4、1、8、9、5、10、6、2、0]。

性质 1：二叉树的 前序遍历 序列，根结点一定是 最先 访问到的结点；
性质 2：二叉树的 后序遍历 序列，根结点一定是 最后 访问到的结点；
性质 3：根结点把二叉树的 中序遍历 序列划分成两个部分，第一部分的所有结点构成了根结点的左子树，第二部分的所有结点构成了根结点的右子树。

图的深度优先遍历

深度优先遍历有「回头」的过程，在树中由于不存在「环」（回路），对于每一个结点来说，每一个结点只会被递归处理一次。而「图」中由于存在「环」（回路），就需要 记录已经被递归处理的结点（通常使用布尔数组或者哈希表），以免结点被重复遍历到。

深度优先遍历的两种实现方式

在深度优先遍历的过程中，需要将 当前遍历到的结点 的相邻结点 暂时保存 起来，以便在回退的时候可以继续访问它们。遍历到的结点的顺序呈现「后进先出」的特点，因此 深度优先遍历可以通过「栈」实现。

深度优先遍历有以下两种方式：

编写递归方法；
编写栈，通过迭代的方式实现。

深度优先的应用

应用 1：获得图（树）的一些属性

104. 二叉树的最大深度（简单）

func maxDepth(root *TreeNode) int {
    if root == nil {
        return 0
    }
    queue :=[]*TreeNode{root}       // 辅助队列,根节点入队
    depth := 0                  // 初始化深度为0

    for len(queue) > 0 { // 当队列不为空时，循环以下操作
        size := len(queue)//当前队列中元素个数size作为限定:当前层级中节点数量
        for i := 0; i < size; i++ { // 遍历当前层级中的节点
            s := queue[0]      // 获取队首元素
            if s.Left != nil { // 如果左子树不为空，左子树入队
                queue = append(queue, s.Left)
            }
            if s.Right != nil { // 如果右子树不为空，右子树入队
                queue = append(queue, s.Right)
            }
            queue = queue[1:]  // 队首元素出队
        }
        depth++ // for循环结束后这一层级节点已经访问结束，深度加+1
    }
    return depth
}

111. 二叉树的最小深度【简单/BFS/DFS】

// ============== 解法一： BFS 迭代实现，广度优先遍历 ================
// https://www.cnblogs.com/Lusai/p/15709094.html
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
 
 
func minDepth(root *TreeNode) int {
    if root == nil {
        return 0
    }
    queue :=[]*TreeNode{root}     // 查找队列,将起点加入队列
    depth := 1                  // root 本身就是一层，depth初始化为1
    for len(queue)!=0{
        size := len(queue)
        // 将当前队列中的所有结点向四周扩散
        for i := 0; i < size; i++ {
            cur := queue[0]
            // 判断是否到终点
            if cur.Left == nil && cur.Right == nil {
                return depth
            }
            // 将 cur的相邻节点加入队列
            if cur.Left != nil {
                queue = append(queue, cur.Left)
            }
            if cur.Right != nil {
                queue = append(queue, cur.Right)
            }
            // 去掉当前节点
            queue = queue[1:]
        }
        // 这里增加深度
        depth++
    }
    return depth
}



// ============== 解法二： DFS   ================

func minDepth(root *TreeNode) int {
    if root == nil {
        return 0
    }
    if root.Left != nil && root.Right == nil {
        return 1 + minDepth(root.Left)
    }
    if root.Right != nil && root.Left == nil {
        return 1 + minDepth(root.Right)
    }
    return 1 + Min(minDepth(root.Left), minDepth(root.Right))
}

112. 路径总和(简单)

113. 路径总和 II（中等）

翻转二叉树

相同的树

对称二叉树

求根到叶子节点数字之和

236. 二叉树的最近公共祖先（中等）

 

// ======  解法二 利用hash表和存储走过的路 ==============
/*
思路：我们可以用哈希表存储所有节点的父节点，然后我们就可以利用节点的父节点信息从 p 结点开始不断往上跳，并记录已经访问过的节点
，再从 q 节点开始不断往上跳，如果碰到已经访问过的节点，那么这个节点就是我们要找的最近公共祖先。
算法：
从根节点开始遍历整棵二叉树，用哈希表记录每个节点的父节点指针。
从 p 节点开始不断往它的祖先移动，并用数据结构记录已经访问过的祖先节点。
同样，我们再从 q 节点开始不断往它的祖先移动，如果有祖先已经被访问过，即意味着这是 p 和 q 的深度最深的公共祖先，即 LCA 节点。
*/

func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
    parent := map[int]*TreeNode{}
    visited := map[int]bool{}

    var dfs func(*TreeNode)

    dfs = func(r *TreeNode) {
        if r == nil {
            return
        }
        if r.Left != nil {
            parent[r.Left.Val] = r
            dfs(r.Left)
        }
        if r.Right != nil {
            parent[r.Right.Val] = r
            dfs(r.Right)
        }
    }

    dfs(root)

    for p != nil {
        visited[p.Val] = true
        p = parent[p.Val]
    }
    for q != nil {
        if visited[q.Val] {
            return q
        }
        q = parent[q.Val]
    }

    return nil

}


// func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
//  if root == nil {
//      return nil
//  }

//  // 如果p,q为根节点，则公共祖先为根节点
//  if root.Val == p.Val || root.Val == q.Val {
//      return root
//  }

//  // 如果p,q在左子树，则公共祖先在左子树查找
//  if find(root.Left, p) && find(root.Left, q) {
//      return lowestCommonAncestor(root.Left, p, q)
//  }

//  // 如果p,q在右子树，则公共祖先在右子树查找
//  if find(root.Right, p) && find(root.Right, q) {
//      return lowestCommonAncestor(root.Right, p, q)

//  }

//  // 如果p,q分属两侧，则公共祖先为根节点
//  return root

// }

// func find(root, c *TreeNode) bool {
//  if root == nil {
//      return false
//  }
//  if root.Val == c.Val {
//      return true
//  }
//  return find(root.Left, c) || find(root.Right, c)
// }

从前序与中序遍历序列构造二叉树

从中序与后序遍历序列构造二叉树

前序遍历构造二叉搜索树

从先序遍历还原二叉树

二叉树的前序遍历

应用 2：计算无向图的连通分量

323

应用 3：检测图中是否存在环

第 684 题：冗余连接（中等）

第 802 题：找到最终的安全状态（中等）

应用 4：二分图检测

第 785 题：判断二分图（中等）

应用 5：拓扑排序

第 210 题：课程表 II（中等）

应用 6：回溯算法获得一个问题所有的解

回溯算法是深度优先遍历思想的应用.回溯算法是一种通过不断 尝试 ，搜索一个问题的一个解或者 所有解 的方法。在求解的过程中，如果继续求解不能得到题目要求的结果，就需要 回退 到上一步尝试新的求解路径。回溯算法的核心思想是：在一棵 隐式的树（看不见的树） 上进行一次深度优先遍历。
完成「力扣」第 22 题：括号生成（中等）；
完成「力扣」第 17 题：电话号码的字母组合（中等）；
完成「力扣」第 784 题：字母大小写全排列（中等）。

Leetcode题

利用DFS通杀岛屿系列

二叉树遍历框架

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

func traverse(root *TreeNode) {
   traverse(root.Left)
   traverse(root.Right)
}

二维矩阵的 DFS 代码框架

// 二维矩阵遍历框架一
func dfs_array(grid [][]int, visited [][]bool, i int, j int) {
   row, col := len(grid), len(grid[0])
   if i < 0 || i >= row || j < 0 || j >= col || visited[i][j] {
      return
   }
   visited[i][j] = true
   dfs_array(grid, visited, i-1, j) // 上
   dfs_array(grid, visited, i+1, j) // 下
   dfs_array(grid, visited, i, j-1) // 左
   dfs_array(grid, visited, i, j+1) // 右
}


// 二维矩阵遍历框架二
func dfs_array2(grid [][]int, visited [][]bool, i int, j int) {
    dir := [][]int{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}
    row, col := len(grid), len(grid[0])
    if i < 0 || i >= row || j < 0 || j >= col || visited[i][j] {
        return
    }
    visited[i][j] = true
    for _, v := range dir {
        next_row := i + v[0]
        next_col := j + v[1]
        dfs_array2(grid, visited, next_row, next_col)
    }
}

200. 岛屿数量(中等)

给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。此外，你可以假设该网格的四条边均被水包围。

输入：grid = [["1","1","1","1","0"],["1","1","0","1","0"],["1","1","0","0","0"],["0","0","0","0","0"]]
输出：1

输入：grid = [["1","1","0","0","0"],["1","1","0","0","0"],["0","0","1","0","0"],["0","0","0","1","1"]]
输出：3

func main() {
    grid := [][]byte{
        {'1', '1', '0', '0', '0'},
        {'1', '1', '0', '0', '0'},
        {'1', '1', '0', '0', '0'},
        {'1', '1', '0', '0', '0'},
        {'0', '0', '1', '0', '0'},
        {'0', '0', '0', '1', '1'}}
    fmt.Println(numIslands(grid))
}

/*
============   解法一： DFS ========================
思路：
先找到岛屿，然后利用DFS将岛屿周边相连的都变为海，这里不用visited来记录了，可以直接利用=海来剪枝
*/
func numIslands(grid [][]byte) int {
    row, col := len(grid), len(grid[0])

    res := 0
    for i := 0; i < row; i++ {
        for j := 0; j < col; j++ {
            if grid[i][j] == '1' {
                res++
                dfs_array2(grid, i, j)
            }
        }
    }
    return res

}

// 二维矩阵遍历框架二
func dfs_array2(grid [][]byte, i int, j int) {
    dir := [][]int{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}
    row, col := len(grid), len(grid[0])
    if i < 0 || i >= row || j < 0 || j >= col || grid[i][j] == '0' {
        return
    }
    grid[i][j] = '0'
    for _, v := range dir {
        next_row := i + v[0]
        next_col := j + v[1]
        dfs_array2(grid, next_row, next_col)
    }
}

1254. 统计封闭岛屿的数目(中等)

二维矩阵 grid 由 0 （土地）和 1 （水）组成。岛是由最大的4个方向连通的 0 组成的群，封闭岛是一个 完全 由1包围（左、上、右、下）的岛。请返回 封闭岛屿 的数目。

输入：grid = [[1,1,1,1,1,1,1,0],[1,0,0,0,0,1,1,0],[1,0,1,0,1,1,1,0],[1,0,0,0,0,1,0,1],[1,1,1,1,1,1,1,0]]
输出：2
解释：
灰色区域的岛屿是封闭岛屿，因为这座岛屿完全被水域包围（即被 1 区域包围）。那么如何判断「封闭岛屿」呢？其实很简单，把那些靠边的岛屿排除掉，剩下的不就是 封闭岛屿

func main() {
    grid := [][]int{
        {1, 1, 1, 1, 1, 1, 1, 0},
        {1, 0, 0, 0, 0, 1, 1, 0},
        {1, 0, 1, 0, 1, 1, 1, 0},
        {1, 0, 0, 0, 0, 1, 0, 1},
        {1, 1, 1, 1, 1, 1, 1, 0}}
    fmt.Println(closedIsland(grid))
}

/*
===========  解法一： DFS  ===========
先把周边的岛屿直接填海，再来做题，相当于数据进行一个预处理。
*/
func closedIsland(grid [][]int) int {
    row, col := len(grid), len(grid[0])
    for j := 0; j < col; j++ {
        dfs_array(grid, 0, j)     // 把靠上边的岛屿淹掉
        dfs_array(grid, row-1, j) // 把靠下边的岛屿淹掉
    }

    for i := 0; i < row; i++ {
        dfs_array(grid, i, 0)     // 把靠左边的岛屿淹掉
        dfs_array(grid, i, col-1) // 把靠右边的岛屿淹掉
    }

    res := 0
    for i := 0; i < row; i++ {
        for j := 0; j < col; j++ {
            if grid[i][j] == 0 { // 此题中0是岛
                res++
                dfs_array(grid, i, j) // 因为连在一起算是一个岛，所以这里是把连在一起的全都找出来，填海
            }
        }
    }
    return res
}

// 二维矩阵遍历框架二
func dfs_array(grid [][]int, i int, j int) {
    dir := [][]int{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}
    row, col := len(grid), len(grid[0])
    if i < 0 || i >= row || j < 0 || j >= col || grid[i][j] == 1 { // 此题中1是海
        return
    }
    grid[i][j] = 1
    for _, v := range dir {
        next_row := i + v[0]
        next_col := j + v[1]
        dfs_array(grid, next_row, next_col)
    }
}

1020. 飞地的数量(中等)

给你一个大小为 m x n 的二进制矩阵 grid ，其中 0 表示一个海洋单元格、1 表示一个陆地单元格。
一次 移动 是指从一个陆地单元格走到另一个相邻（上、下、左、右）的陆地单元格或跨过 grid 的边界。
返回网格中 无法 在任意次数的移动中离开网格边界的陆地单元格的数量。

输入：grid = [[0,0,0,0],[1,0,1,0],[0,1,1,0],[0,0,0,0]]
输出：3
解释：有三个 1 被 0 包围。一个 1 没有被包围，因为它在边界上。

输入：grid = [[0,1,1,0],[0,0,1,0],[0,0,1,0],[0,0,0,0]]
输出：0
解释：所有 1 都在边界上或可以到达边界。

func main() {
    grid := [][]int{{0, 0, 0, 0}, {1, 0, 1, 0}, {0, 1, 1, 0}, {0, 0, 0, 0}}
    fmt.Println(numEnclaves(grid))
}

func numEnclaves(grid [][]int) int {
    // 先数据预处理一下，把靠边的岛屿都填成海
    row, col := len(grid), len(grid[0])
    for j := 0; j < col; j++ {
        dfs_array(grid, 0, j)     // 把靠上边的岛屿淹掉
        dfs_array(grid, row-1, j) // 把靠下边的岛屿淹掉
    }

    for i := 0; i < row; i++ {
        dfs_array(grid, i, 0)     // 把靠左边的岛屿淹掉
        dfs_array(grid, i, col-1) // 把靠右边的岛屿淹掉
    }

    res := 0
    for i := 0; i < row; i++ {
        for j := 0; j < col; j++ {
            if grid[i][j] == 1 { // 此题中1是岛
                res++
            }
        }
    }
    return res
}

func dfs_array(grid [][]int, i int, j int) {
    dir := [][]int{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}
    row, col := len(grid), len(grid[0])
    if i < 0 || i >= row || j < 0 || j >= col || grid[i][j] == 0 { // 此题中0是海
        return
    }
    grid[i][j] = 0
    for _, v := range dir {
        next_row := i + v[0]
        next_col := j + v[1]
        dfs_array(grid, next_row, next_col)
    }
}

695. 岛屿的最大面积（中等）

给你一个大小为 m x n 的二进制矩阵 grid 。岛屿 是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在 水平或者竖直的四个方向上 相邻。你可以假设 grid 的四个边缘都被 0（代表水）包围着。岛屿的面积是岛上值为 1 的单元格的数目。计算并返回 grid 中最大的岛屿面积。如果没有岛屿，则返回面积为 0 。

输入：grid = [[0,0,1,0,0,0,0,1,0,0,0,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,1,1,0,1,0,0,0,0,0,0,0,0],[0,1,0,0,1,1,0,0,1,0,1,0,0],[0,1,0,0,1,1,0,0,1,1,1,0,0],[0,0,0,0,0,0,0,0,0,0,1,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,0,0,0,0,0,0,1,1,0,0,0,0]]
输出：6
解释：答案不应该是 11 ，因为岛屿只能包含水平或垂直这四个方向上的 1 。

[图片上传失败...(image-f9303f-1671480093471)]

// ================  解法一： DFS ===================
func maxAreaOfIsland(grid [][]int) int {
    row, col := len(grid), len(grid[0])

    res := 0
    for i := 0; i < row; i++ {
        for j := 0; j < col; j++ {
            if grid[i][j] == 1 { // 此题中1是岛
                res = max(res, dfs_array(grid, i, j))
            }
        }
    }
    return res

}

func dfs_array(grid [][]int, i int, j int) int {
    dir := [][]int{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}
    row, col := len(grid), len(grid[0])
    if i < 0 || i >= row || j < 0 || j >= col || grid[i][j] == 0 { // 此题中0是海
        return 0
    }
    grid[i][j] = 0
    count := 1 // 其实这里设置为1，真的很不好理解
    for _, v := range dir {
        next_row := i + v[0]
        next_col := j + v[1]
        count += dfs_array(grid, next_row, next_col)
    }
    return count
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

// ============== 解法二： BFS =========
func maxAreaOfIsland(grid [][]int) int {
    row, col := len(grid), len(grid[0])
    dir := [][]int{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}
    ans := 0

    // 这里还真不能一次性把所有的岛头都找出来，因为找头是找=1，如果不伴随着填海一起找，会有问题。
    for i := 0; i < row; i++ {
        for j := 0; j < col; j++ {
            if grid[i][j] == 0 {
                continue
            }

            // 这里一定要注意，找到岛屿的头，然后加入queue, count要从1开始，然后再把岛屿的头填为海
            queue := [][]int{{i, j}} // 找到头
            count := 1
            grid[i][j] = 0

            for len(queue) != 0 {
                top := queue[0]
                for _, v := range dir {
                    newRow, newCol := top[0]+v[0], top[1]+v[1]
                    if newRow < 0 || newRow >= row || newCol < 0 || newCol >= col || grid[newRow][newCol] == 0 {
                        continue
                    }
                    grid[newRow][newCol] = 0
                    count++
                    queue = append(queue, []int{newRow, newCol})
                }
                queue = queue[1:]
            }
            ans = max(ans, count)
        }
    }
    return ans

}

1905. 统计子岛屿（中等）

给你两个 m x n 的二进制矩阵 grid1 和 grid2 ，它们只包含 0 （表示水域）和 1 （表示陆地）。一个 岛屿 是由 四个方向 （水平或者竖直）上相邻的 1 组成的区域。任何矩阵以外的区域都视为水域。

如果 grid2 的一个岛屿，被 grid1 的一个岛屿 完全 包含，也就是说 grid2 中该岛屿的每一个格子都被 grid1 中同一个岛屿完全包含，那么我们称 grid2 中的这个岛屿为 子岛屿 。

请你返回 grid2 中 子岛屿 的 数目 。

输入：grid1 = {{1,1,1,0,0},{0,1,1,1,1},{0,0,0,0,0},{1,0,0,0,0},{1,1,0,1,1}}, grid2 = {{1,1,1,0,0},{0,0,1,1,1},{0,1,0,0,0},{1,0,1,1,0},{0,1,0,1,0}}
输出：3
解释：如上图所示，左边为 grid1 ，右边为 grid2 。
grid2 中标红的 1 区域是子岛屿，总共有 3 个子岛屿。

[图片上传失败...(image-58379c-1671480093471)]

func main() {
    grid1 := [][]int{
        {1, 1, 1, 0, 0},
        {0, 1, 1, 1, 1},
        {0, 0, 0, 0, 0},
        {1, 0, 0, 0, 0},
        {1, 1, 0, 1, 1}}
    grid2 := [][]int{
        {1, 1, 1, 0, 0},
        {0, 0, 1, 1, 1},
        {0, 1, 0, 0, 0},
        {1, 0, 1, 1, 0},
        {0, 1, 0, 1, 0}}

    fmt.Println(countSubIslands(grid1, grid2))
}

/*
什么情况下 grid2 中的一个岛屿 B 是 grid1 中的一个岛屿 A 的子岛？
当岛屿 B 中所有陆地在岛屿 A 中也是陆地的时候，岛屿 B 是岛屿 A 的子岛。
反过来说，如果岛屿 B 中存在一片陆地，在岛屿 A 的对应位置是海水，那么岛屿 B 就不是岛屿 A 的子岛。
只要遍历 grid2 中的所有岛屿，把那些不可能是子岛的岛屿排除掉，剩下的就是子岛。
*/

func countSubIslands(grid1 [][]int, grid2 [][]int) int {
    // 先数据预处理一下
    row, col := len(grid1), len(grid1[0])
    for i := 0; i < row; i++ {
        for j := 0; j < col; j++ {
            if grid2[i][j] == 1 && grid1[i][j] == 0 {
                dfs_array(grid2, i, j)
            }
        }
    }

    // 现在 grid2 中剩下的岛屿都是子岛，计算岛屿数量
    res := 0
    for i := 0; i < row; i++ {
        for j := 0; j < col; j++ {
            if grid2[i][j] == 1 {
                res++
                dfs_array(grid2, i, j)
            }
        }
    }
    return res

}

func dfs_array(grid [][]int, i int, j int) {
    dir := [][]int{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}
    row, col := len(grid), len(grid[0])
    if i < 0 || i >= row || j < 0 || j >= col || grid[i][j] == 0 { // 此题中0是海
        return
    }
    grid[i][j] = 0
    for _, v := range dir {
        next_row := i + v[0]
        next_col := j + v[1]
        dfs_array(grid, next_row, next_col)
    }
}

回溯算法 （处理 排列-组合-子集 问题）

回溯算法和我们常说的 DFS 算法非常类似，本质上就是一种暴力穷举算法。回溯算法和 DFS 算法的细微差别是：**回溯算法是在遍历「树枝」，DFS 算法是在遍历「节点」。

https://labuladong.gitee.io/algo/4/31/106/

216. 组合总和 III（中等）

找出所有相加之和为 n 的 k 个数的组合，且满足下列条件:
只使用数字1到9
每个数字 最多使用一次 
返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回。

输入: k = 3, n = 7
输出: [[1,2,4]]
解释:
1 + 2 + 4 = 7
没有其他符合的组合了。

输入: k = 3, n = 9
输出: [[1,2,6], [1,3,5], [2,3,4]]
解释:
1 + 2 + 6 = 9
1 + 3 + 5 = 9
2 + 3 + 4 = 9
没有其他符合的组合了。
 
输入: k = 4, n = 1
输出: []
解释: 不存在有效的组合。
在[1,9]范围内使用4个不同的数字，我们可以得到的最小和是1+2+3+4 = 10，因为10 > 1，没有有效的组合。

39. 组合总和（中等）

给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。 对于给定的输入，保证和为 target 的不同组合数少于 150 个。

输入：candidates = [2,3,6,7], target = 7
输出：[[2,2,3],[7]]
解释：
2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。
7 也是一个候选， 7 = 7 。
仅有这两种组合。

输入: candidates = [2,3,5], target = 8
输出: [[2,2,2,2],[2,3,3],[3,5]]

40. 组合总和 II(中等)

给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。candidates 中的每个数字在每个组合中只能使用 一次 。
注意：解集不能包含重复的组合。 

输入: candidates = [10,1,2,7,6,1,5], target = 8,
输出:[[1,1,6],[1,2,5],[1,7],[2,6]]

输入: candidates = [2,5,2,1,2], target = 5,
输出:[[1,2,2],[5]]

46. 全排列（中等）

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

输入：nums = [0,1]
输出：[[0,1],[1,0]]

输入：nums = [1]
输出：[[1]]

47. 全排列 II（中等）

给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。

输入：nums = [1,1,2]
输出：[[1,1,2],[1,2,1],[2,1,1]]
 
输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

77. 组合(中等)

给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。你可以按 任何顺序 返回答案。

输入：n = 4, k = 2
输出：[[2,4],[3,4],[2,3],[1,2],[1,3],[1,4],]

输入：n = 1, k = 1
输出：[[1]]

78. 子集（中等）

给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

输入：nums = [0]
输出：[[],[0]]

90. 子集 II（中等）

给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。

输入：nums = [1,2,2]
输出：[[],[1],[1,2],[1,2,2],[2],[2,2]]

输入：nums = [0]
输出：[[],[0]]

剑指 Offer II 079. 所有子集（中等）

给定一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

输入：nums = [0]
输出：[[],[0]]

剑指 Offer II 080. 含有 k 个元素的组合（中等）

给定两个整数 n 和 k，返回 1 ... n 中所有可能的 k 个数的组合。

输入: n = 4, k = 2
输出:
[ [2,4],[3,4],[2,3],[1,2],[1,3],[1,4]]

输入: n = 1, k = 1
输出: [[1]]

291. 单词规律 II（会员/中等）

给你一种规律 pattern 和一个字符串 s，请你判断 s 是否和 pattern 的规律相匹配。如果存在单个字符到字符串的 双射映射 ，那么字符串 s 匹配 pattern ，即：如果pattern 中的每个字符都被它映射到的字符串替换，那么最终的字符串则为 s 。双射 意味着映射双方一一对应，不会存在两个字符映射到同一个字符串，也不会存在一个字符分别映射到两个不同的字符串。

输入：pattern = "abab", s = "redblueredblue"
输出：true
解释：一种可能的映射如下：
'a' -> "red"
'b' -> "blue"

输入：pattern = "aaaa", s = "asdasdasdasd"
输出：true
解释：一种可能的映射如下：
'a' -> "asd"

320. 列举单词的全部缩写（会员/中等）

单词的 广义缩写词 可以通过下述步骤构造：先取任意数量的 不重叠、不相邻 的子字符串，再用它们各自的长度进行替换。

例如，"abcde" 可以缩写为：
"a3e"（"bcd" 变为 "3" ）
"1bcd1"（"a" 和 "e" 都变为 "1"）
"5" ("abcde" 变为 "5")
"abcde" (没有子字符串被代替)
然而，这些缩写是 无效的 ：
"23"（"ab" 变为 "2" ，"cde" 变为 "3" ）是无效的，因为被选择的字符串是相邻的
"22de" ("ab" 变为 "2" ， "bc" 变为 "2")  是无效的，因为被选择的字符串是重叠的
给你一个字符串 word ，返回 一个由 word 的所有可能 广义缩写词 组成的列表 。按 任意顺序 返回答案。

 
输入：word = "word"
输出：["4","3d","2r1","2rd","1o2","1o1d","1or1","1ord","w3","w2d","w1r1","w1rd","wo2","wo1d","wor1","word"]

输入：word = "a"
输出：["1","a"]