今日任务：

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

资料来源：

1. 代码随想录 | LeetCode93 复原IP地址
2. 代码随想录 | LeetCode78 子集
3. 代码随想录 | LeetCode90 子集Ⅱ

1 LeetCode93 复原IP地址

输入：s = "25525511135"
输出：["255.255.11.135","255.255.111.35"]

输入：s = "0000"
输出：["0.0.0.0"]

输入：s = "101023"
输出：["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]

一个比较另类的切割问题，我这个写法属于是有点绕远路，思路走的还是子集问题的思路，其实没有必要将选取的字符还取出来存着，用一个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 子集

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

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

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

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 子集Ⅱ

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

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

这是子集问题+树层查重，使用的方法就是哈希数组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()