今日任务：

1. 回溯算法总结
2. LeetCode332 重新安排行程（没写）
3. LeetCode51 N皇后（没写）
4. LeetCode37 解数独（没写）



资料来源：

1. [代码随想录 | 回溯算法总结](https://programmercarl.com/%E5%9B%9E%E6%BA%AF%E6%80%BB%E7%BB%93.html)
2. [代码随想录 | LeetCode332 重新安排行程](https://programmercarl.com/0332.%E9%87%8D%E6%96%B0%E5%AE%89%E6%8E%92%E8%A1%8C%E7%A8%8B.html)
3. [代码随想录 | LeetCode51 N皇后](https://programmercarl.com/0051.N%E7%9A%87%E5%90%8E.html)
4. [代码随想录 | LeetCode37 解数独](https://programmercarl.com/0037.%E8%A7%A3%E6%95%B0%E7%8B%AC.html)

### 1 回溯算法总结

回溯算法最重要的就是**如何将要解决的问题映射到那颗具体的回溯的树上去**，比如说今天的332和37，一旦能想明白这一点，剩下的就不难了。

**回溯算法模板**：

```
def __init__():
    self.path = []
    self.result = []
    self.题目给定资料...
    
def 入口函数():
    self.题目给定资料赋值
    back_tracking()
    return self.result
    
def back_tracking():
    if 终止条件:
        self.result.append(self.path.copy())
    return
    
    for 单层递归循环
        if 符合条件:
            self.path.append()
            self.back_tracking()  向下递归
            self.path.pop()
```

**回溯算法查重问题**：

根据这几天的题来说，查重有两个问题：**在哪里查？具体查谁？**

1. 在哪里查？
    
    - 树枝查重：生效范围是所有的递归函数，需要在类变量里记录重复元素/下标
    - 树层查重：生效范围是同一层的所有递归函数，需要在上一层的递归函数中记录重复元素/下标或者对题目给定元素进行排序从而在循环中检查前后元素来查重
    - 递归查重：生效范围是单个递归函数内，需要在单个递归函数中记录重复元素/下标

    递归查重和树层查重本身是有相似性的，递归查重可以说就是树层查重另一个版本。但是为了分的清楚点还是分开讨论比较好。
    
3. 具体查谁？
    - 查元素是否重复：要记录的是元素本身，除了通过哈希数组num_used来记录该元素的值是否被用过以外，也可以对题目给定元素进行排序从而在循环中检查前后元素来查重
    - 查下标是否重复：要记录的是元素的位置，只能通过哈希数组index_used来记录该元素是否被用过

**回溯算法参数加不加start_index？**

分情况讨论。如果下一层递归的循环需要从上一层指定位置开始，就需要start_index参数；如果下一层递归的循环可以从头开始/开始位置不和上一层递归有所关联，那么就不需要start_index参数。

代码随想录算法训练营第三十天 | 回溯算法总结

代码随想录算法训练营第二十九天 | LeetCode491 递增子序列、LeetCode46 全排列、LeetCode47 全排列Ⅱ

今日任务：

1. LeetCode93 复原IP地址
2. LeetCode78 子集
3. LeetCode90 子集Ⅱ



资料来源：

1. [代码随想录 | LeetCode93 复原IP地址](https://programmercarl.com/0093.%E5%A4%8D%E5%8E%9FIP%E5%9C%B0%E5%9D%80.html)
2. [代码随想录 | LeetCode78 子集](https://programmercarl.com/0078.%E5%AD%90%E9%9B%86.html)
3. [代码随想录 | LeetCode90 子集Ⅱ](https://programmercarl.com/0090.%E5%AD%90%E9%9B%86II.html)

### 1 LeetCode93 复原IP地址

:::info{title="题目"}
有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。

例如："0.1.2.201" 和 "192.168.1.1" 是 有效 IP 地址，但是 "0.011.255.245"、"192.168.1.312" 和 "192.168@1.1" 是 无效 IP 地址。
给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入 '.' 来形成。你 不能 重新排序或删除 s 中的任何数字。你可以按 任何 顺序返回答案。

 

示例 1：
```
输入：s = "25525511135"
输出：["255.255.11.135","255.255.111.35"]
```
示例 2：
```
输入：s = "0000"
输出：["0.0.0.0"]
```
示例 3：
```
输入：s = "101023"
输出：["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]
```

提示：

- 1 <= s.length <= 20
- s 仅由数字组成
:::

一个比较另类的切割问题，我这个写法属于是有点绕远路，思路走的还是子集问题的思路，其实没有必要将选取的字符还取出来存着，用一个index表示切割的位置就好了。

``` python
from typing import List

class Solution:
    def __init__(self):
        self.s = ""
        self.path = []
        self.result: List[str] = []

    def restoreIpAddresses(self, s: str) -> List[str]:
        self.s = s
        self.back_tracking(0, 1)
        for i in range(len(self.result)):
            self.result[i] = self.result[i][:-1]
        return self.result

    def back_tracking(self, start_index: int, recursion_number: int):
        # recursion_number的作用是记录递归层数 也是记录目前回溯出来的IP地址的段数 递归层数 + 1 = IP地址的段数
        
        # 终止条件
        result = "".join(self.path)
        if len(result) == len(self.s) + 4 and recursion_number == 5:
            self.result.append(result)

        # 剪枝
        if recursion_number > 5:
            return

        # 单层递归逻辑
        part_of_ip = ""
        for i in range(start_index, len(self.s)):
            part_of_ip += self.s[i]
            if (1 <= int(part_of_ip) <= 255 and part_of_ip[0] != "0") or part_of_ip == "0":  # 检查选取的数字是否符合标准
                part_of_ip += "."
                self.path.append(part_of_ip)
                self.back_tracking(i + 1, recursion_number + 1)  # 递归层数 + 1 IP地址的段数 + 1
                self.path.pop()
                part_of_ip = part_of_ip[:-1]
```       

### 2 LeetCode78 子集

:::info{title="题目"}
给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的
子集
（幂集）。

解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

示例 1：
```
输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
```
示例 2：
```
输入：nums = [0]
输出：[[],[0]]
```

提示：

- 1 <= nums.length <= 10
- -10 <= nums[i] <= 10
- nums 中的所有元素 互不相同
:::

非常标准的回溯写法，只是注意子集问题要找树的所有节点，所以每次进递归都要添加元素，不设添加标准。终止条件还是要有的（就本题而言没有其实也行）。

``` python
from typing import List

class Solution:
    def __init__(self):
        self.nums = []
        self.path = []
        self.result = []

    def subsets(self, nums: List[int]) -> List[List[int]]:
        self.nums = nums
        self.back_tracking(0)
        return self.result

    def back_tracking(self, start_index: int):
        self.result.append(self.path.copy())
        if len(self.path) == len(self.nums):  # 这个终止条件不必要 反正真的到终止的时候下面的循环也没法开始
            return

        for i in range(start_index, len(self.nums)):
            self.path.append(self.nums[i])
            self.back_tracking(i + 1)
            self.path.pop()
``` 

### 3 LeetCode90 子集Ⅱ

:::info{title="题目"}
给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的 
子集
（幂集）。

解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。

示例 1：
```
输入：nums = [1,2,2]
输出：[[],[1],[1,2],[1,2,2],[2],[2,2]]
```
示例 2：
```
输入：nums = [0]
输出：[[],[0]]
```

提示：

- 1 <= nums.length <= 10
- -10 <= nums[i] <= 10
:::

这是子集问题+树层查重，使用的方法就是哈希数组num_used。

``` python
from typing import List

class Solution:
    def __init__(self):
        self.path = []
        self.result = []
        self.nums = []

    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        self.nums = nums
        self.back_tracking(0)
        return self.result

    def back_tracking(self, start_index: int):
        self.result.append(self.path.copy())
        if len(self.path) == len(self.nums):
            return

        used_num_hash = [0] * 21
        for i in range(start_index, len(self.nums)):
            if used_num_hash[self.nums[i]] == 0:  # 检查是否被使用
                self.path.append(self.nums[i])
                used_num_hash[self.nums[i]] = 1
                self.back_tracking(i + 1)
                self.path.pop()
```

代码随想录算法训练营第二十八天 | LeetCode93 复原IP地址、LeetCode78 子集、LeetCode90 子集Ⅱ

今日任务：

1. LeetCode39 组合总和
2. LeetCode40 组合总和 Ⅱ
3. LeetCode131 分割回文串



资料来源：

1. [代码随想录 | LeetCode39 组合总和]()
2. [代码随想录 | LeetCode40 组合总和 Ⅱ]()
3. [代码随想录 | LeetCode131 分割回文串]()

### 1 LeetCode39 组合总和

:::info{title="题目"}
给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。

candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。 

对于给定的输入，保证和为 target 的不同组合数少于 150 个。

 

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

提示：

- 1 <= candidates.length <= 30
- 2 <= candidates[i] <= 40
- candidates 的所有元素 互不相同
- 1 <= target <= 40
:::

回溯秒了。这题是无重复元素，同时说明可以无限制地挑选元素，那在递归到下一层的时候，仍然将当前元素选上就可以了。

:::tip{title="提示"}
start_index，这样的变量用来指示每一层的递归从哪里开始。一般情况下，**如果是从单个集合中取元素组成组合/排列，那么是要用start_index来指示下一层递归的循环从哪里开始**；如果是从多个集合中取元素组成组合的话，因为每个元素都是从0开始循环，所以可以不用start_index来记录循环应该从哪里开始。

注意这个start_index是记录循环从哪里开始的，而上一个电话号码的题不需要这个记录。之所以上一题的写法中也有index，是因为它记录的是数字长度（即递归深度）。
:::

``` python
from typing import List

class Solution:
    def __init__(self):
        self.candidates = []
        self.target = 0
        self.path = []
        self.result = []

    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        self.target = target
        self.candidates = candidates
        self.recursion(0)
        return self.result

    def recursion(self, index):
        if sum(self.path) == self.target:
            self.result.append(self.path.copy())
        if sum(self.path) > self.target:
            return
        for i in range(index, len(self.candidates)):
            self.path.append(self.candidates[i])
            self.recursion(i)  # 递归到下一层时 不要+1 这样下一层循环开始时仍然会加这个元素
            self.path.pop()
```        

另外，这题可以通过对给定的数组进行排序来合理剪枝。

### 2 LeetCode40 组合总和 Ⅱ

:::info{title="题目"}
给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用 一次 。

注意：解集不能包含重复的组合。 

 

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

提示:

- 1 <= candidates.length <= 100
- 1 <= candidates[i] <= 50
- 1 <= target <= 30
:::

和上一个题的区别在于，给定的数组不是无重复的了，而且要求每个元素只能取一次，因此需要在树层上进行去重。

:::tip{title="提示"}
关于回溯中的去重，一共有三种：树枝去重、树层去重和递归去重。

以本题为例，如果candidates为[1, 1, 2]，那么回溯形成的树是这样的：

![4efc6caaf18530245c83c5dc6c0b99b.jpg](https://www.misaka19327.cc/static/img/fd6a3a7a31dc0faa1eb756b6e9ee4bf2.4efc6caaf18530245c83c5dc6c0b99b.jpg)

在这题的语境下，如果要用树层查重，那么题目要求应该是“解集不能包含重复的组合”；如果要用树枝查重，那么题目就应该要求“解集中的组合中不能包含重复的元素”。总的来说，如果是只对单个结果内的元素进行查重，就要考虑树枝查重；如果是对所有结果进行查重，就要考虑树层查重。

树枝查重常用的方法是定义一个和题目给定数组长度相同的数组index_used，每次向path数组中添加元素时，先检查该元素在题目给定数组的下标在index_used的位置是否为0。如果不为0，则说明该元素已经被使用过，直接跳过该元素；如果为0，则说明该元素还没有被使用过，照常添加元素的同时将index_used对应位置置1。在递归回来的时候，还需要将对应位置置0。

树层查重常用的方法是先对题目给定的数组进行排序，然后每次循环的时候从第二个元素开始检查，是否和上一个元素相同，相同就跳过该元素。

还有一种比较特殊的查重是针对单次递归的查重，例子就是491 递增子序列，需要特殊分析。它需要根据题目给定数组中元素可能值设置哈希数组num_used，每次向path中添加元素时，需要在num_used中进行检查。
:::

``` python
from typing import List

class Solution:
    def __init__(self):
        self.candidates = []
        self.target = 0
        self.path = []
        self.result = []

    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        self.target = target
        candidates.sort()
        self.candidates = candidates
        self.recursion(0)
        return self.result

    def recursion(self, index):
        if sum(self.path) == self.target:
            self.result.append(self.path.copy())
        if sum(self.path) > self.target:
            return
        for i in range(index, len(self.candidates)):
            if i != index:
                if self.candidates[i] == self.candidates[i - 1]:
                    continue
            self.path.append(self.candidates[i])
            self.recursion(i + 1)
            self.path.pop()
```            

### 3 LeetCode131 分割回文串

:::info{title="题目"}
给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 
回文串
 。返回 s 所有可能的分割方案。

 

示例 1：
```
输入：s = "aab"
输出：[["a","a","b"],["aa","b"]]
```
示例 2：
```
输入：s = "a"
输出：[["a"]]
```

提示：

- 1 <= s.length <= 16
- s 仅由小写英文字母组成
:::

回溯秒了。这道题如果能看出怎么回溯的话就不难，难的就是怎么把它和回溯的思考过程匹配上。组合和排列问题很好匹配，递归的深度就是一次组合/排列的过程，循环的长度就是在已经确定的部分下的其他所有可能性。而切割问题也是可以依照这个思路去思考的。

![f837e1852502359b7130b2fcd3637df.jpg](https://www.misaka19327.cc/static/img/680123a5985639dd795b742615f0120f.f837e1852502359b7130b2fcd3637df.jpg)

判断是否为回文串，双指针就好。

``` python
from typing import List

class Solution:
    def __init__(self):
        self.path = []
        self.s = ""
        self.result = []

    def partition(self, s: str) -> List[List[str]]:
        self.s = s
        self.back_tracking(0)
        return self.result

    def is_palindrome(self, s: str) -> bool:
        forward_index, last_index = 0, len(s) - 1
        while forward_index <= last_index:
            if s[forward_index] != s[last_index]:
                return False
            forward_index += 1
            last_index -= 1
        return True

    def back_tracking(self, index: int):
        if index == len(self.s):
            self.result.append(self.path.copy())
        temp = ""
        for i in range(index, len(self.s)):
            temp += self.s[i]
            if self.is_palindrome(temp):
                self.path.append(temp)
                self.back_tracking(i + 1)
                self.path.pop()
```

代码随想录算法训练营第二十七天 | LeetCode39 组合总和、LeetCode40 组合总和 Ⅱ、LeetCode131 分割回文串

今日任务：

1. LeetCode216 组合总和Ⅲ
2. LeetCode17 电话号码的字母组合



资料来源：

1. [代码随想录 | LeetCode216 组合总和Ⅲ](https://programmercarl.com/0216.%E7%BB%84%E5%90%88%E6%80%BB%E5%92%8CIII.html)
2. [代码随想录 | LeetCode17 电话号码的字母组合](https://programmercarl.com/0017.%E7%94%B5%E8%AF%9D%E5%8F%B7%E7%A0%81%E7%9A%84%E5%AD%97%E6%AF%8D%E7%BB%84%E5%90%88.html)

### 1 LeetCode216 组合总和Ⅲ

:::info{title="题目"}
找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：

只使用数字1到9
每个数字 最多使用一次 
返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回。

 

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

提示:

- 2 <= k <= 9
- 1 <= n <= 60
:::

回溯秒了。

``` python
from typing import List

class Solution:
    def __init__(self):
        self.path = []
        self.target_sum = 0
        self.target_length = 0
        self.result = []

    def combinationSum3(self, k: int, n: int) -> List[List[int]]:
        self.target_sum = n
        self.target_length = k
        self.resursion(0)
        return self.result

    def resursion(self, num_added: int):
        if sum(self.path) == self.target_sum and len(self.path) == self.target_length:
            self.result.append(self.path.copy())
            return
        for i in range(num_added + 1, 10):
            self.path.append(i)
            self.resursion(i)
            self.path.pop()
        return
```       

和昨天的题一样，可以剪枝。

``` python
# 剪枝版本
from typing import List


# leetcode submit region begin(Prohibit modification and deletion)
class Solution:
    def __init__(self):
        self.path = []
        self.target_sum = 0
        self.target_length = 0
        self.result = []

    def combinationSum3(self, k: int, n: int) -> List[List[int]]:
        self.target_sum = n
        self.target_length = k
        self.resursion(0)
        return self.result

    def resursion(self, num_added: int):
        if len(self.path) > self.target_length:
            return
        if sum(self.path) == self.target_sum and len(self.path) == self.target_length:
            self.result.append(self.path.copy())
            return
        # 剪枝 1 目前已经有多长 len(self.path)
        # 2 目前还需要多长 self.target_length - len(self.path)
        # 3 所以循环到什么位置 range(num_added + 1, 10 - (self.target_length - len(self.path)))
        for i in range(num_added + 1, 10 - (self.target_length - len(self.path)) + 1):
            self.path.append(i)
            self.resursion(i)
            self.path.pop()
        return
```        

### 2 LeetCode17 电话号码的字母组合

:::info{title="题目"}
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

示例 1：
```
输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
```
示例 2：
```
输入：digits = ""
输出：[]
```
示例 3：
```
输入：digits = "2"
输出：["a","b","c"]
```

提示：

- 0 <= digits.length <= 4
- digits[i] 是范围 ['2', '9'] 的一个数字。
:::

回溯一样秒。先建立数字到字符串的映射（可以优化为数组），按传入的字符串长度决定递归深度，每个数字对应的字母数量决定for次数，最后递归回来记得回溯就行。

:::tip{title="提示"}
python做传列表参数或者两个列表互相append的时候如果出问题，优先考虑要不要copy。
:::

``` python
from typing import List

class Solution:
    def __init__(self):
        self.map = {2: "abc", 3: "def", 4: "ghi", 5: "jkl", 6: "mno", 7: "pqrs", 8: "tuv", 9: "wxyz"}
        self.path = []
        self.result = []
        self.digits = []

    def letterCombinations(self, digits: str) -> List[str]:
        if digits == "":
            return []
        self.digits = list(digits)
        self.recursion(0)
        result_ = []
        for i in self.result:
            result_.append("".join(i))
        return result_

    def recursion(self, index: int):
        if index == len(self.digits):
            self.result.append(self.path.copy())
            return
        chars = self.map.get(int(self.digits[index]))
        for i in chars:
            self.path.append(i)
            self.recursion(index + 1)
            self.path.pop()
```