39. 组合总和
难度中等
给定一个无重复元素的数组 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]
]
1 class Solution: 2 def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]: 3 res = list() 4 candidates.sort() 5 size = len(candidates) 6 self.__dfs(candidates, size, target, list(), res) 7 new_res = self.__duplicate_removal(res) 8 return new_res 9 10 def __dfs(self, candidates: List[int], size:int, residue: int, path: list, res: list): 11 if residue == 0: 12 res.append(path[:]) 13 return 14 for index in range(size): 15 if candidates[index] > residue: 16 break 17 path.append(candidates[index]) 18 self.__dfs(candidates, size, residue-candidates[index], path, res) 19 path.pop() 20 21 def __duplicate_removal(self, res: list): 22 new_res = list() 23 for each_element in res: 24 each_element.sort() 25 if each_element not in new_res: 26 new_res.append(each_element) 27 return new_res
1 class Solution: 2 def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]: 3 candidates.sort() 4 size = len(candidates) 5 res = self.__dfs(candidates, size, target, list()) 6 new_res = self.__duplicate_removal(res) 7 8 return new_res 9 10 11 def __dfs(self, candidates: List[int], size:int, residue: int, path: list)-> List[List[int]]: 12 if residue == 0: 13 return [path] 14 15 if residue < 0: 16 return list() 17 18 res = list() 19 for index in range(size): 20 if candidates[index] > residue: 21 break 22 temp_res = self.__dfs(candidates, size, residue-candidates[index], path+[candidates[index]]) 23 res += temp_res 24 25 return res 26 27 28 def __duplicate_removal(self, res: list) -> List[List[int]]: 29 new_res = list() 30 for each_element in res: 31 each_element.sort() 32 if each_element not in new_res: 33 new_res.append(each_element) 34 35 return new_res
40. 组合总和 II
难度中等
给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用一次。
说明：
- 所有数字（包括目标数）都是正整数。
- 解集不能包含重复的组合。
示例 1:
输入: candidates =[10,1,2,7,6,1,5], target =8, 所求解集为: [ [1, 7], [1, 2, 5], [2, 6], [1, 1, 6] ]
示例 2:
输入: candidates = [2,5,2,1,2], target = 5, 所求解集为: [ [1,2,2], [5] ]
1 class Solution: 2 def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]: 3 candidates.sort() 4 res = list() 5 self.__dfs(candidates, target, 0, len(candidates), list(), res) 6 return res 7 8 9 def __dfs(self, candidates: List[int], residue: int, start:int, size:int, path:list, res: list): 10 if residue == 0: 11 res.append(path[:]) 12 return 13 14 for index in range(start, size): 15 if candidates[index] > residue: 16 break 17 18 if index > start and candidates[index-1] == candidates[index]: 19 continue 20 21 self.__dfs(candidates, residue - candidates[index], index + 1, size, path+[candidates[index]], res) 22
1 class Solution: 2 def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]: 3 candidates.sort() 4 res = self.__dfs(candidates, target, 0, len(candidates), list()) 5 6 return res 7 8 9 def __dfs(self, candidates: List[int], residue: int, start:int, size:int, path:list): 10 if residue == 0: 11 12 return [path] 13 14 if residue < 0: 15 16 return list() 17 18 res = list() 19 for index in range(start, size): 20 if candidates[index] > residue: 21 break 22 if index > start and candidates[index-1] == candidates[index]: 23 continue 24 25 temp_res = self.__dfs(candidates, residue-candidates[index], index+1, size, path + [candidates[index]]) 26 res += temp_res 27 28 return res
46. 全排列
难度中等
给定一个没有重复数字的序列，返回其所有可能的全排列。
示例:
输入: [1,2,3] 输出: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ]
1 class Solution: 2 def permute(self, nums: List[int]) -> List[List[int]]: 3 nums.sort() 4 res = self.__dfs(nums, len(nums), list()) 5 6 return res 7 8 9 def __dfs(self, nums: List[int], size:int, path:list) -> List[List[int]]: 10 if size == 0: 11 return [path] 12 13 res = list() 14 for index in range(size): 15 temp_res = self.__dfs(nums[0:index]+nums[index+1:], size-1, path+[nums[index]]) 16 res += temp_res 17 18 return res
47. 全排列 II
难度中等
给定一个可包含重复数字的序列，返回所有不重复的全排列。
示例:
输入: [1,1,2] 输出: [ [1,1,2], [1,2,1], [2,1,1] ]
1 class Solution: 2 def permuteUnique(self, nums: List[int]) -> List[List[int]]: 3 nums.sort() 4 res = self.__dfs(nums, len(nums), list()) 5 6 return res 7 8 9 def __dfs(self, nums: List[int], size:int, path:list) -> List[List[int]]: 10 if size == 0: 11 return [path] 12 13 res = list() 14 for index in range(size): 15 if index > 0 and nums[index-1] == nums[index]: 16 continue 17 temp_res = self.__dfs(nums[0:index]+nums[index+1:], size-1, path+[nums[index]]) 18 res += temp_res 19 20 return res
77. 组合
难度中等
给定两个整数 n 和 k，返回 1 ... n 中所有可能的 k 个数的组合。
示例:
输入: n = 4, k = 2 输出: [ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4], ]
1 class Solution: 2 3 def combine(self, n: int, k: int) -> List[List[int]]: 4 if n <= 0 or k <= 0 or k > n: 5 return [] 6 result_list = list() 7 self.combine_pre(0, n, k, list(), result_list) 8 return result_list 9 10 def combine_pre(self, begin:int, n: int, k:int, inter_list:list, result_list:list) : 11 if k == 0: 12 result_list.append(inter_list[:]) 13 return 14 for index in range(begin, n): 15 self.combine_pre(index+1, n, k-1, inter_list+[index+1], result_list)
1 class Solution: 2 3 def combine(self, n: int, k: int) -> List[List[int]]: 4 if n <= 0 or k <= 0 or k > n: 5 return [] 6 7 result_list = self.combine_pre(0, n, k, list()) 8 9 return result_list 10 11 12 def combine_pre(self, begin:int, n: int, k:int, inter_list:list) : 13 if k == 0: 14 return [inter_list] 15 16 result_list = list() 17 for index in range(begin, n): 18 temp_res = self.combine_pre(index+1, n, k-1, inter_list+[index+1]) 19 result_list += temp_res 20 21 return result_list
216. 组合总和 III
难度中等
找出所有相加之和为 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]]
1 class Solution: 2 def combinationSum3(self, k: int, n: int) -> List[List[int]]: 3 res = list() 4 self.__dfs(k, n, 0, list(), res) 5 6 return res 7 8 9 def __dfs(self, k: int, residue: int, start:int, path:list, res: list): 10 11 if k == 0: 12 if residue ==0: 13 res.append(path[:]) 14 return 15 16 for index in range(start, 9): 17 if index + 1 > residue: 18 break 19 self.__dfs(k-1, residue-index-1, index+1, path+[index+1], res)
1 def __dfs(self, k: int, residue: int, start:int, path:list) -> List[List[int]]: 2 3 if k == 0 and residue ==0: 4 return [path] 5 6 if k < 0 or residue < 0: 7 return list() 8 9 res = list() 10 for index in range(start, 9): 11 if index + 1 > residue: 12 break 13 temp_res = self.__dfs(k-1, residue-index-1, index+1, path+[index+1]) 14 res += temp_res 15 16 return res 17 18 19 def combinationSum3(self, k: int, n: int) -> List[List[int]]: 20 res = self.__dfs(k, n, 0, list()) 21 22 return res
93. 复原IP地址
难度中等
给定一个只包含数字的字符串，复原它并返回所有可能的 IP 地址格式。
示例:
输入: "25525511135" 输出:["255.255.11.135", "255.255.111.35"]
1 from typing import List 2 3 class Solution: 4 def restoreIpAddresses(self, s: str) -> List[str]: 5 s_len = len(s) 6 if s_len < 4 and s_len > 12: 7 return list() 8 9 res = list() 10 self.dfs(s, s_len, 0, 0, list(), res) 11 12 return [".".join(res_item) for res_item in res] 13 14 15 def dfs(self, s, size, split_times, begin, path, res): 16 if begin == size: 17 if split_times == 4: 18 res.append(path[:]) 19 return 20 21 if size - begin < (4 - split_times) or size - begin > 3*(4 - split_times): 22 return 23 24 for index in range(3): 25 if begin + index >= size: 26 return 27 28 ip_segment = self.judge_if_ip_segment(s, begin, begin + index) 29 30 if ip_segment != -1: 31 self.dfs(s, size, split_times+1, begin+index+1, path+[str(ip_segment)], res) 32 33 34 def judge_if_ip_segment(self, s, left, right): 35 size = right - left + 1 36 if size > 1 and s[left] == '0': 37 return -1 38 39 res = 0 40 for i in range(left, right + 1): 41 res = 10*res + (ord(s[i])-ord('0')) 42 if res > 255: 43 return -1 44 45 return res