代码随想录算法训练营第二十七天|组合总和等

77 组合

1 描述

给定两个整数 n 和 k，返回 1 ... n 中所有可能的 k 个数的组合。

示例: 输入: n = 4, k = 2 输出: [ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4], ]

2 代码

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        path = []
        rst = []
        
        def helper(start):
            end = n + 1 - (k - len(path) - 1)
            for i in range(start, end):
                path.append(i)
                if len(path) == k:
                    rst.append(path[:])
                else:
                    helper(i + 1)
                path.pop()
            return
        
        helper(1)
        return rst

?3 总结?

• python 的参数传递，参考Python里参数是值传递还是引用传递？ - 知乎 (zhihu.com)
• global 关键字 与 nonlocal 关键字的用法（主要针对不可变对象）?

?216.组合总和III

1 描述

找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。

说明：

• 所有数字都是正整数。
• 解集不能包含重复的组合。

示例 1: 输入: k = 3, n = 7 输出: [[1,2,4]]

示例 2: 输入: k = 3, n = 9 输出: [[1,2,6], [1,3,5], [2,3,4]]

2 代码

class Solution:
    def __init__(self):
        self.path = []
        self.sum_ = 0
        self.rst = []
        
    def combinationSum3(self, k: int, n: int) -> List[List[int]]:
    
        def helper(start):
            end = 10 - (k - len(self.path) - 1)
            for i in range(start, end):
                self.path.append(i)
                self.sum_ += i
                if len(self.path) == k and self.sum_ == n:
                    self.rst.append(self.path[:])
                elif len(self.path) < k and self.sum_ < n:
                    helper(i + 1)
                self.path.pop()
                self.sum_ -= i
            return
        
        helper(1)
        return self.rst

17.电话号码的字母组合

1 描述

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。

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

示例:

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

说明：尽管上面的答案是按字典序排列的，但是你可以任意选择答案输出的顺序。

2 代码

class Solution:
    def __init__(self):
        self.d = {
            '2':['a', 'b', 'c'],
            '3':['d', 'e', 'f'],
            '4':['g', 'h', 'i'],
            '5':['j', 'k', 'l'],
            '6':['m', 'n', 'o'],
            '7':['p', 'q', 'r', 's'],
            '8':['t', 'u', 'v'],
            '9':['w', 'x', 'y', 'z'],
        }
        self.path = []
        self.rst = []
    
    def letterCombinations(self, digits: str) -> List[str]:
        if not digits:
            return []

        def helper(i):
            if i == len(digits):
                self.rst.append(''.join(self.path))
                return

            for c in self.d[digits[i]]:
                self.path.append(c)
                helper(i + 1)
                self.path.pop()
        
        helper(0)
        return self.rst

39. 组合总和

1 描述

给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的数字可以无限制重复被选取。

说明：

• 所有数字（包括 target）都是正整数。
• 解集不能包含重复的组合。

示例 1：

• 输入：candidates = [2,3,6,7], target = 7,
• 所求解集为： [ [7], [2,2,3] ]

示例 2：

• 输入：candidates = [2,3,5], target = 8,
• 所求解集为： [ [2,2,2,2], [2,3,3], [3,5] ]

2 代码

class Solution:
    def __init__(self):
        self.path = []
        self.sum_ = 0
        self.rst = []

    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:

        def helper(start):
            for i in range(start, len(candidates)):
                self.path.append(candidates[i])
                self.sum_ += candidates[i]
                if self.sum_ < target:
                    helper(i)
                elif self.sum_ == target:
                    self.rst.append(self.path[:])
                self.path.pop()
                self.sum_ -= candidates[i]
            return
        
        helper(0)
        return self.rst

40.组合总和II

1 描述

给定一个候选人编号的集合?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

2 代码

class Solution:
    def __init__(self):
        self.path = []
        self.rst = []
        self.sum_ = 0

    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        candidates.sort() 

        def helper(start):
            for i in range(start, len(candidates)):
                if i > start and candidates[i] == candidates[i - 1]:
                    continue
                
                self.path.append(candidates[i])
                self.sum_ += candidates[i]
                if self.sum_ == target:
                    self.rst.append(self.path[:])
                elif self.sum_ < target:
                    helper(i + 1)
                else:
                    self.path.pop()
                    self.sum_ -= candidates[i]
                    break
                self.path.pop()
                self.sum_ -= candidates[i]
        
        helper(0)
        return self.rst

?