image.png
0. 鏈接
1. 題目
Given a set of candidate numbers (candidates) (without duplicates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target.
The same repeated number may be chosen from candidates unlimited number of times.
Note:
All numbers (including target) will be positive integers.
The solution set must not contain duplicate combinations.
Example 1:
Input: candidates = [2,3,6,7], target = 7,
A solution set is:
[
[7],
[2,2,3]
]
Example 2:
Input: candidates = [2,3,5], target = 8,
A solution set is:
[
[2,2,2,2],
[2,3,3],
[3,5]
]
2. 思路：先升序排列，再深度優(yōu)先搜索
- 先升序排列待選列表
- 遍歷處理每個待選值
- 對于每個值a，先假設(shè)其進(jìn)入假設(shè)集，然后繼續(xù)從大于等于a的數(shù)里深度搜索后續(xù)值(優(yōu)先重復(fù)選取，條件是剩余量需要大于或等于a)，直到這些值的和等于目標(biāo)值，則找到了一個合法的假設(shè)集，然后將這個假設(shè)集添加到結(jié)果列表里
3. 代碼
# coding:utf8
from typing import List
import time
class Solution:
def find(self, nums, nums_len, begin_idx, results, temp_result, target):
if begin_idx >= nums_len:
return
left_half = target // 2
for i in range(begin_idx, nums_len):
num = nums[i]
if num <= left_half:
temp_result.append(num)
self.find(nums, nums_len, i, results, temp_result, target - num)
temp_result.pop(-1)
elif num == target:
results.append(temp_result + [num])
elif num > target:
break
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
candidates.sort()
results, temp_result = list(), list()
self.find(candidates, len(candidates), 0, results, temp_result, target)
return results
class Solution1:
def find(self, nums, begin_idx, results, temp_result, target):
if begin_idx >= len(nums):
return
left_half = target // 2
for i in range(begin_idx, len(nums)):
num = nums[i]
if num <= left_half:
temp_result.append(num)
self.find(nums, i, results, temp_result, target - num)
temp_result.pop(-1)
elif num == target:
results.append(temp_result + [num])
elif num > target:
break
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
candidates.sort()
results, temp_result = list(), list()
self.find(candidates, 0, results, temp_result, target)
return results
class Solution2:
def find(self, nums, results, temp_result, target):
if not nums:
return
left_half = target // 2
for i, num in enumerate(nums):
num = nums[i]
if num <= left_half:
temp_result.append(num)
self.find(nums[i:], results, temp_result, target - num)
temp_result.pop(-1)
elif num == target:
results.append(temp_result + [num])
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
candidates.sort()
results, temp_result = list(), list()
self.find(candidates, results, temp_result, target)
return results
def log_cost_time(func):
def _log(*args, **kwargs):
start_time = time.time()
func(*args, **kwargs)
end_time = time.time()
print("cost time:{}秒".format(end_time - start_time))
return _log
@log_cost_time
def solution(type=0):
s = None
if type == 0:
s = Solution()
elif type == 1:
s = Solution1()
elif type == 2:
s = Solution2()
else:
print("wrong type, need value 0/1/2")
return
count = 10000
result = None
while count > 0:
result = s.combinationSum([2, 3, 6, 7, 8, 9], 7)
count -= 1
print(result)
solution(0)
solution(1)
solution(2)
輸出結(jié)果
[[2, 2, 3], [7]]
cost time:0.06700396537780762秒
[[2, 2, 3], [7]]
cost time:0.07000374794006348秒
[[2, 2, 3], [7]]
cost time:0.07800459861755371秒
可以看到，多謝@渡_02a8
建設(shè)性的意見，經(jīng)過優(yōu)化后的代碼，對同一數(shù)據(jù)跑10000次的結(jié)果，耗時明顯減少。
4. 結(jié)果
image.png
