Content:
- 题目17：Letter Combinations of a Phone Number
- 题目39：Combination Sum
- 题目40：Combination Sum II
- 题目77：Combinations
- 题目78：Subsets
- 题目90：Subsets II
- 题目216：Combination Sum III
题目17：Letter Combinations of a Phone Number
内容：
Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. Return the answer in any order.
A mapping of digit to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.
Example 1:
Input: digits = "23"
Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]
Example 2:
Input: digits = ""
Output: []
Example 3:
Input: digits = "2"
Output: ["a","b","c"]
Constraints:
0 <= digits.length <= 4digits[i]is a digit in the range['2', '9'].
思路：
遍历结点
代码实现：
###解法1: DFS
mapletter = [" ","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"]
def letterCombinations(self, digits: str) -> List[str]:
result = []
if not digits:
return []
def dfs(digits,l,current,result):
if l == len(digits):
if l > 0:
result.append("".join(current))
return
for i in self.mapletter[int(digits[l])]:
current[l] = i
dfs(digits, l+1, current, result)
cur = ['' for _ in range(len(digits))]
dfs(digits, 0, cur, result)
return result
###解法2: 列表生成器
def letterCombinations(self, digits: str) -> List[str]:
mapletter = {
'2':"abc",
'3': "def",
'4': "ghi",
'5': "jkl",
'6': "mno",
'7': "pqrs",
'8': "tuv",
'9': "wxyz"
}
if not digits:
return []
result = ['']
for i in digits:
result = [p+q for p in result for q in mapletter[i] ]
return result
题目39：Combination Sum
内容：
Given an array of distinct integers candidates and a target integer target, return a list of all unique combinations of candidates where the chosen numbers sum to target. You may return the combinations in any order.
The same number may be chosen from candidates an unlimited number of times. Two combinations are unique if the frequency of at least one of the chosen numbers is different.
It is guaranteed that the number of unique combinations that sum up to target is less than 150 combinations for the given input.
Example 1:
Input: candidates = [2,3,6,7], target = 7
Output: [[2,2,3],[7]]
Explanation:
2 and 3 are candidates, and 2 + 2 + 3 = 7. Note that 2 can be used multiple times.
7 is a candidate, and 7 = 7.
These are the only two combinations.
Example 2:
Input: candidates = [2,3,5], target = 8
Output: [[2,2,2,2],[2,3,3],[3,5]]
Example 3:
Input: candidates = [2], target = 1
Output: []
Example 4:
Input: candidates = [1], target = 1
Output: [[1]]
Example 5:
Input: candidates = [1], target = 2
Output: [[1,1]]
Constraints:
1 <= candidates.length <= 301 <= candidates[i] <= 200- All elements of
candidatesare distinct. 1 <= target <= 500
思路：
- 像这种从组合中选取某些数字从而达到与目标值一样的需求，一般都是要先给组合排序，让组合从小到大，或者从大到小。
- 组合里面的数可以重复使用，即代表当符合特定要求的前提下（譬如该值比目标值小），每次递归时仍然需要从该索引开始搜索，而不是从下一个索引开始。
- 使用DFS时，有可能会超时，所以要考虑剪枝。
代码实现：
###解法: DFS
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
if not target or not candidates:
return []
def dfs(target, ind, cur, ans):
if target == 0:
ans.append(cur)
return
for i in range(ind, len(candidates)):
if candidates[i]> target:
return
dfs(target-candidates[i], i, cur+[candidates[i]], ans)
candidates.sort()
result = []
dfs(target, 0, [], result)
return result
分析：
if target == 0是dfs的出口，代表本轮的dfs已找到结果，保存其结果到ans中if candidates[i]> target是剪枝操作。cur+[candidates[i]]是一个trick。正常来说，一个数组作为参数，其内存地址是不会改变，即使将其插入到结果中，插入的亦只是该数组的内存地址。但使用list + [value]的方式，其实等于有又创建了一个新的数组，并将cur变量指向新的数组内存地址，所以空间复杂度是会增加。
题目40：Combination Sum II
内容：
Given a collection of candidate numbers (candidates) and a target number (target), find all unique combinations in candidates where the candidate numbers sum to target.
Each number in candidates may only be used once in the combination.
Note: The solution set must not contain duplicate combinations.
Example 1:
Input: candidates = [10,1,2,7,6,1,5], target = 8
Output:
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]
Example 2:
Input: candidates = [2,5,2,1,2], target = 5
Output:
[
[1,2,2],
[5]
]
Constraints:
1 <= candidates.length <= 1001 <= candidates[i] <= 501 <= target <= 30
思路：
像这种从组合中选取某些数字从而达到与目标值一样的需求，一般都是要先给组合排序，让组合从小到大，或者从大到小。
与39题不同的是，组合里面的数只能用一次。即代表使用了该当前索引值后，下一个dfs要从下一个索引开始。
得出的结果是不能有重复。可以想到的方法有两个
使用set数据结构，最后再将结果转换成list
在每次寻找结果的for循环中，在同一个索引位置中不允许重复数字出现。即出现数字重复时直接跳过，因为前一个索引（同一个数字）已经完成了筛选。
- 前提条件是组合必须要事先经过排列。
代码实现：
###解法: DFS
def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
if not target or not candidates:
return []
def dfs(target, ind, cur, ans):
if target == 0:
ans.append(cur)
return
for i in range(ind, len(candidates)):
if candidates[i] > target:
return
if i > ind and candidates[i] == candidates[i-1]:
continue
dfs(target-candidates[i], i+1, cur+[candidates[i]], ans)
candidates.sort()
result = []
dfs(target, 0, [], result)
return result
分析：
该题的关键点就是数据不能重复。筛选重复的数据就是通过该条命令
if i > ind and candidates[i] == candidates[i-1]: continue具体意思看思路的解释。
题目77：Combinations
内容：
Given two integers n and k, return all possible combinations of k numbers out of 1 ... n.
You may return the answer in any order.
Example 1:
Input: n = 4, k = 2
Output:
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]
Example 2:
Input: n = 1, k = 1
Output: [[1]]
Constraints:
1 <= n <= 201 <= k <= n
思路：
- n 和 k是从1开始，所以for循环的序号要从1开始。
- 题目列出所有的可能，没有其他隐藏问题，关键点就是有可能会超时，所以要适当剪枝。
代码实现：
###解法: DFS
###剪枝缩小
def combine(self, n: int, k: int) -> List[List[int]]:
if k == 1 and n ==1:
return [[1]]
def dfs(ind, cur, ans):
if len(cur) == k:
ans.append(cur)
return
for i in range(ind, n + 1):
if (k - len(cur) + ind) > n + 1:
return
dfs(i+1, cur+[i], ans)
result = []
dfs(1, [], result)
return result
### 常规做法（有可能会超时）
def combine(self, n: int, k: int) -> List[List[int]]:
if k == 1 and n ==1:
return [[1]]
def dfs(ind, cur, ans):
if len(cur) == k:
ans.append(cur)
return
for i in range(ind, n + 1）:
dfs(i+1, cur+[i], ans)
result = []
dfs(1, [], result)
return result
分析：
关于
(k - len(cur) + ind) > n + 1的解析：如果目标k的长度是5，当前已进行的cur长度是2，那么还需要3 次才能完成。而且需要确保从当前的index开始，能够不超出n的大小（python要到n+1才能使用n的值）。当需要的步数超出
n+1，已经不能满足结果的需求，没有当前的for循环没必要继续执行下去，返回至上一层。
题目78：Subsets
内容：
Given an integer array nums, return all possible subsets (the power set).
The solution set must not contain duplicate subsets.
Example 1:
Input: nums = [1,2,3]
Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
Example 2:
Input: nums = [0]
Output: [[],[0]]
Constraints:
1 <= nums.length <= 10-10 <= nums[i] <= 10
思路：
- 输出所有的子集，即假如nums长度为3，需要输出长度为0,1,2,3的所有子集。
代码实现：
###解法: DFS
def subsets(self, nums: List[int]) -> List[List[int]]:
l = len(nums)
def dfs(idx, cur, ans):
if len(cur) <= l:
ans.append(cur[:])
for i in range(idx, l):
dfs(i+1, cur+ [nums[i]], ans)
result = []
dfs(0, [], result)
return result
题目90：Subsets II
内容：
Given a collection of integers that might contain duplicates, *nums*, return all possible subsets (the power set).
Note: The solution set must not contain duplicate subsets.
Example:
Input: [1,2,2]
Output:
[
[2],
[1],
[1,2,2],
[2,2],
[1,2],
[]
]
思路：
- 输出所有的子集，即假如nums长度为3，需要输出长度为0,1,2,3的所有子集。
- 不能有重复子集的出现，参考第40题的思路即可
代码实现：
###解法: DFS
def subsets(self, nums: List[int]) -> List[List[int]]:
nums.sort()
l = len(nums)
def dfs(idx, cur, ans):
if len(cur) <= l:
ans.append(cur[:])
for i in range(idx, l):
if i > idx and nums[i] == nums[i-1]:
continue
dfs(i+1, cur+ [nums[i]], ans)
result = []
dfs(0, [], result)
return result
题目216：Combination Sum III
内容：
Find all valid combinations of k numbers that sum up to n such that the following conditions are true:
- Only numbers
1through9are used. - Each number is used at most once.
Return a list of all possible valid combinations. The list must not contain the same combination twice, and the combinations may be returned in any order.
Example 1:
Input: k = 3, n = 7
Output: [[1,2,4]]
Explanation:
1 + 2 + 4 = 7
There are no other valid combinations.
Example 2:
Input: k = 3, n = 9
Output: [[1,2,6],[1,3,5],[2,3,4]]
Explanation:
1 + 2 + 6 = 9
1 + 3 + 5 = 9
2 + 3 + 4 = 9
There are no other valid combinations.
Example 3:
Input: k = 4, n = 1
Output: []
Explanation: There are no valid combinations. [1,2,1] is not valid because 1 is used twice.
Example 4:
Input: k = 3, n = 2
Output: []
Explanation: There are no valid combinations.
Example 5:
Input: k = 9, n = 45
Output: [[1,2,3,4,5,6,7,8,9]]
Explanation:
1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 = 45
There are no other valid combinations.
Constraints:
2 <= k <= 91 <= n <= 60
思路：
- 数字从1-9，每次只能使用一次，所以要使用permutation的方式，即要标记该数字当前是否已被使用
代码实现：
###解法: DFS
def combinationSum3(self, k: int, n: int) -> List[List[int]]:
used = [ 0 for i in range(10)]
def dfs(last, used, idx, cur, ans):
if last == 0 and len(cur) == k:
ans.append(cur[:])
return
for i in range(idx, 10):
if used[i] or i > last:
continue
used[i] = 1
dfs(last-i, used, i+1, cur+[i], ans)
used[i] = 0
result =[]
dfs(n, used, 1, [], result)
return result
分析：
- 首先创建一个used数组，用来标记数字是否已被使用。创建10元素的原因是可以直接利用索引号来使用数字。这里使用
0作为未使用，1作为已使用。 - 当元素未被使用，要被使用的时候需要将其标记。用完后，需要将标记清零。
- 当元素已被使用，或者当前元素大于剩余结果时，返回上一层。
- 当剩余结果为0，且数组的元素个数符合要求时，保存其结果。
There are 0 comments