代码随想录算法训练营第二十九天 | 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()
```