【基础算法精讲-学习记录】回溯1

视频学习记录

https://www.bilibili.com/video/BV1mG4y1A7Gu/?

• 回溯，主要是问自己三个问题：当前操作是什么，子问题是什么，下一个子问题是什么

• 本次主要学的是子集型回溯，特点是每个元素都可以选或不选，由此就有两个解答思路：

  1. 从输入（元素）角度：每个递归都是判断一个元素选或不选；
  2. 从答案角度：每个递归是在比上回更小的子问题上遍历元素，间接排除了不同递归层次重复选择子问题的情况；

例题和课后作业代码记录

17. 电话号码的字母组合

https://leetcode.cn/problems/letter-combinations-of-a-phone-number/description/

MAPPING = {
    "2": "abc",
    "3": "def",
    "4": "ghi",
    "5": "jkl",
    "6": "mno",
    "7": "pqrs",
    "8": "tuv",
    "9": "wxyz",
}

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        ans = []
        path = []
        n = len(digits)
        def dfs(i): # 这里的i指的是正在遍历digits的下标
            if i == n:
                ans.append(''.join(path))
                return 

            for c in MAPPING[digits[i]]: # 选
                path.append(c)
                dfs(i+1)
                path.pop()
        dfs(0)
        return ans

78. 子集

https://leetcode.cn/problems/subsets/description/

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        ans = []
        path = []
        n = len(nums)
        def dfs(i): # 这里的i指的是正在遍历nums的下标
            if i == n:
                ans.append(path.copy())
                return 
            
            dfs(i+1)

            path.append(nums[i])
            dfs(i+1)
            path.pop()

        dfs(0)
        return ans

131. 分割回文串

https://leetcode.cn/problems/palindrome-partitioning/description/

class Solution:
    def partition(self, s: str) -> List[List[str]]:
        ans = []
        n = len(s)
        path = []
        
        def dfs(i): # 将分割回文串视为在字符之间加点或不加点
            if i == n:
                ans.append(path.copy())
                return 

            for j in range(i+1, n+1):
                cur_path = s[i:j]
                # print(cur_path)
                if cur_path == cur_path[::-1]:
                    path.append(cur_path)
                    dfs(j)
                    path.pop()
                
        dfs(0)
        return ans

257. 二叉树的所有路径

https://leetcode.cn/problems/binary-tree-paths/description/

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:
        ans = []
        path = []
        def dfs(root):
            if not root:
                return 
            path.append(str(root.val))
            son_cnt = 0
            if root.left:
                dfs(root.left)
                son_cnt += 1
            if root.right:
                dfs(root.right)
                son_cnt += 1
            if son_cnt == 0:
                ans.append("->".join(path))
            path.pop()
        dfs(root)
        return ans
        

113. 路径总和 II

https://leetcode.cn/problems/path-sum-ii/description/

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:
        ans = []
        path = []
        cur_sum = 0
        def dfs(root):
            if not root:
                return 
            nonlocal cur_sum
            path.append(root.val)
            cur_sum += root.val
            if root.left is None and root.right is None:
                if cur_sum == targetSum:
                    ans.append(path.copy())
            else:
                dfs(root.left)
                dfs(root.right)

            cur_sum -= root.val
            path.pop()
        dfs(root)
        return ans

784. 字母大小写全排列

https://leetcode.cn/problems/letter-case-permutation/description/

class Solution:
    def letterCasePermutation(self, s: str) -> List[str]:
        ans = []
        path = ""
        n = len(s)
        def dfs(index:int=0):
            nonlocal path
            if index == n:
                ans.append(path)
                return 
            cur = s[index]
            if "a"<=cur<="z" or "A"<=cur<="Z":
                path += cur.upper()
                dfs(index+1)
                path = path[:-1]
                path += cur.lower()
                dfs(index+1)
                path = path[:-1]
            else:
                path += cur 
                dfs(index+1)
                path = path[:-1]
            
        dfs()
        return ans
            

LCP 51. 烹饪料理

https://leetcode.cn/problems/UEcfPD/description/

class Solution:
    def perfectMenu(self, materials: List[int], cookbooks: List[List[int]], attribute: List[List[int]], limit: int) -> int:
        ans = -1
        n = len(cookbooks)
        def dfs(index:int, cur_delicious:int, cur_eaten:int):
            nonlocal materials, ans
            if index == n:
                if cur_eaten >= limit:
                    ans = max(cur_delicious, ans)
                return 
            dfs(index + 1, cur_delicious, cur_eaten) # 不做当前这个菜
            cur_cookbook = cookbooks[index]
            materials = list(map(lambda x, y: x - y, materials, cur_cookbook))
            enough_materials = True
            for material in materials:
                if material < 0:
                    enough_materials = False 
                    break 
            if enough_materials:
                cur_delicious += attribute[index][0]
                cur_eaten += attribute[index][1]
                dfs(index+1, cur_delicious, cur_eaten)
            materials = list(map(lambda x, y: x + y, materials, cur_cookbook))
        dfs(0, 0, 0)
                
        return ans

2397. 被列覆盖的最多行数

https://leetcode.cn/problems/maximum-rows-covered-by-columns/description/

class Solution:
    def maximumRows(self, matrix: List[List[int]], numSelect: int) -> int:
        row_sum = [sum(r) for r in matrix]
        ans = 0
        n = len(matrix[0])
        m = len(matrix)

        def dfs(col:int, left_num:int):
            nonlocal ans, row_sum
            if left_num == 0 or col == n: # 要么不能选列，要么已经到了边缘
                ans = max(ans, row_sum.count(0))
                print(row_sum)
                return 
            
            dfs(col+1, left_num) # 当前列不选 

            recover_index = []
            for row_index in range(m):
                if matrix[row_index][col] == 1:
                    row_sum[row_index] -=1
                    recover_index.append(row_index)
            

            dfs(col+1, left_num-1) # 选

            for row_index in recover_index:
                row_sum[row_index] += 1

        
        dfs(0, numSelect)
        return ans

1239. 串联字符串的最大长度

https://leetcode.cn/problems/maximum-length-of-a-concatenated-string-with-unique-characters/description/

class Solution:
    def maxLength(self, arr: List[str]) -> int:
        ans = 0
        rec = set()
        n = len(arr)
        def dfs(index:int):
            nonlocal ans, rec
            if index == n:
                ans = max(ans, len(rec))
                return
            dfs(index+1) # 不选

            cur_s = arr[index]
            can_put_in = True 
            ori_rec = rec.copy()
            for c in cur_s:
                if c in rec:
                    can_put_in = False 
                    break 
                rec.update(c)
            
            if can_put_in:
                # print(rec)
                dfs(index+1)
            rec = ori_rec
                
        dfs(0)
        return ans

2212. 射箭比赛中的最大得分

https://leetcode.cn/problems/maximum-points-in-an-archery-competition/description/

class Solution:
    def maximumBobPoints(self, numArrows: int, aliceArrows: List[int]) -> List[int]:
        ans = None 
        max_score = 0
        bobArrows = [0]*12
        cur_score = 0
        def dfs(index:int, leftArrows:int):
            nonlocal max_score, ans, cur_score, bobArrows
            if index == 12: # 限定最多11个区域
                if cur_score > max_score:
                    max_score = cur_score
                    bobArrows[0] += leftArrows
                    ans = bobArrows.copy()
                    bobArrows[0] -= leftArrows
                return 
            
            dfs(index+1, leftArrows) # 不选

            if leftArrows <= 0 or leftArrows <= aliceArrows[index]: # 肯定不选的情况
                return 
            
            cur_score += index 
            bobArrows[index] = aliceArrows[index]+1
            dfs(index+1, leftArrows-bobArrows[index])
            bobArrows[index] = 0
            cur_score -= index

        dfs(0, numArrows)
        return ans

2698. 求一个整数的惩罚数

https://leetcode.cn/problems/find-the-punishment-number-of-an-integer/description/

PRE_SUM = [0]*1001
for i in range(1, 1001):
    s = str(i*i)
    n = len(s)
    def dfs(index:int, cur_sum:int):
        if index == n:
            return cur_sum == i 
        
        accumulate_num = 0
        for j in range(index,n):
            num = int(s[j])
            accumulate_num = accumulate_num*10 + num 
            if dfs(j+1, cur_sum+accumulate_num):
                return True
        return False
    PRE_SUM[i] = PRE_SUM[i-1] + (int(s) if dfs(0, 0) else 0)

class S olution:
    def punishmentNumber(self, n: int) -> int:
        return PRE_SUM[n]

93. 复原 IP 地址

https://leetcode.cn/problems/restore-ip-addresses/description/

class Solution:
    def restoreIpAddresses(self, s: str) -> List[str]:
        ans = []
        cur = []
        n = len(s)
        proper_ip_len = n+3

        def dfs(index:int, phase_cnt:int):
            nonlocal ans, cur 
            if index == n or phase_cnt == 4:
                tmp = '.'.join(cur)
                # print(tmp)
                if len(tmp) == proper_ip_len:
                    ans.append(tmp)
                return 

            for i in range(index, min(index+3, n)):
                cur_s = s[index:i+1]
                if len(cur_s) > 1 and s[index]=="0":
                    break # 有前置零，后面都不用考虑了
                num = int(cur_s)
                if num > 255: # 最后一个循环数字过大
                    break   
                cur.append(cur_s)
                dfs(i+1, phase_cnt+1)
                cur.pop()

        dfs(0, 0)
        return ans