Day 28 卡玛笔记

给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。

你可以按 任何顺序 返回答案。

示例 1：

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

示例 2：

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

回溯法

class Solution:
    def __init__(self):
        self.res=[]
        self.path=[]
    def combine(self, n: int, k: int) -> List[List[int]]:
        self.backtracking(n,k,1)
        return self.res

    def backtracking(self,n,k,startIndex):
        # 递归终止条件
        if len(self.path)==k:
            # 在将路径添加到结果列表时，直接添加self.path会导致所有路径都指向同一个列表对象。
            # 在回溯过程中修改 self.path 时，之前添加到 self.res 中的路径也会被修改。
            self.res.append(self.path.copy())
            return
        
        # 递归逻辑
        for i in range(startIndex,n+1):
            self.path.append(i)
            self.backtracking(n,k,i+1)
            # 回溯
            self.path.pop()

运行结果

剪枝

class Solution:
    def __init__(self):
        self.res=[]
        self.path=[]
    def combine(self, n: int, k: int) -> List[List[int]]:
        self.backtracking(n,k,1)
        return self.res

    def backtracking(self,n,k,startIndex):
        if len(self.path)==k:
            self.res.append(self.path.copy())
            return
        '''
        剪枝操作:就是剪去多余的叶子节点，根据每一层剩下多少个叶子节点来确定for循环右边的数
        (k-len(path))是组合还需要多少个数，比如n=4,k=3
        在第一层时就会剪剩下两个叶子节点（分别是1和2）
        那么就是n-(k-len(path))+1=2,4-(3-0)+1=2
        但是因为是左闭右开区间，所以要多加一个1
        '''
        for i in range(startIndex,n-(k-len(self.path))+2):
            self.path.append(i)
            self.backtracking(n,k,i+1)
            # 回溯
            self.path.pop()

运行结果

找出所有相加之和为 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，没有有效的组合。

回溯法

class Solution:
    
    # 剪枝1是对sum的剪枝
    # 剪枝2是对叶子节点的剪枝

    def __init__(self):
        # 存放结果
        self.res=[]
        # 存放路径
        self.path=[]

    def combine(self,startNum,n,k):
        # 剪枝1：当当前总和大于n，后面循环一定都会大于当前总和，也就是大于n，所以直接返回结果
        if sum(self.path)>n:
            return self.res
        if sum(self.path)==n and len(self.path)==k:
            self.res.append(self.path.copy())
            return
        # 剪枝2：跟上道题一样
        for i in range(startNum,9 - (k - len(self.path)) + 2):
            self.path.append(i)
            self.combine(i+1,n,k)
            self.path.pop()

    def combinationSum3(self, k: int, n: int) -> List[List[int]]:
        self.combine(1,n,k)
        return self.res

运行结果

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

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

示例 1：

输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]

示例 2：

输入：digits = ""
输出：[]

示例 3：

输入：digits = "2"
输出：["a","b","c"]

递归法

class Solution:
    def __init__(self):
        self.res=[]
        self.strs=''
        self.dig={'2':'abc','3':'def','4':'ghi','5':'jkl','6':'mno','7':'pqrs','8':'tuv','9':'wxyz'}
    
    def traversal(self,digits,index):
        # 递归终止条件
        if len(self.strs)==len(digits):
            self.res.append(self.strs[:])
            return

        # 递归逻辑
        for i in self.dig[digits[index]]:
            self.strs+=i
            # index代表当前是第几个按键
            index+=1
            self.traversal(digits,index)
            # 回溯
            self.strs=self.strs[:-1]
            index-=1

    def letterCombinations(self, digits: str) -> List[str]:
        if digits=='':
            return []
        # 将按键转换成列表
        digits=list(digits)
        # 传入下标为0的第一个按键
        self.traversal(digits,0)
        return self.res

运行结果