算法题--给定和，挑选可行的数字列表

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. 思路：先升序排列，再深度优先搜索

• 先升序排列待选列表
• 遍历处理每个待选值
• 对于每个值a，先假设其进入假设集，然后继续从大于等于a的数里深度搜索后续值(优先重复选取，条件是剩余量需要大于或等于a)，直到这些值的和等于目标值，则找到了一个合法的假设集，然后将这个假设集添加到结果列表里

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)

输出结果

[[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
建设性的意见，经过优化后的代码，对同一数据跑10000次的结果，耗时明显减少。

4. 结果

image.png