算法题--给定和，挑选可行的数字列表，同一个位置的元素最多只能使

image.png

0. 链接

题目链接

1. 题目

Given a collection of candidate numbers (candidates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target.

Each number in candidates may only be used once in the combination.

Note:

All numbers (including target) will be positive integers.
The solution set must not contain duplicate combinations.
Example 1:

Input: candidates = [10,1,2,7,6,1,5], target = 8,
A solution set is:
[
  [1, 7],
  [1, 2, 5],
  [2, 6],
  [1, 1, 6]
]

Example 2:

Input: candidates = [2,5,2,1,2], target = 5,
A solution set is:
[
  [1,2,2],
  [5]
]

2. 思路：先升序+去重+深度优先搜索

• 先升序排列排列
• 去重，并记录每个元素的重复次数
• 遍历处理每个待选值
• 对于每个值a，假设其进入假设集，然后

1. 如果在本回合中，a的已使用次数小于前面记录过的a的重复次数，则继续从大于等于a的数里深度搜索后续值(优先重复选取，条件是a小于目标值)，
2. 否则，就要继续从大于a的数里深度搜索了

终止条件：直到这些值的和等于目标值，则找到了一个组合，将其添加到结果二维列表中

• 返回结果二维列表

3. 代码

# coding:utf8
from typing import List


class Solution:
    def find(self, nums: List[int], nums_len: int, begin_idx: int, target: int, results: List[List[int]],
             temp_result: List[int], temp_used_times, nums_times_to_use):
        if begin_idx >= nums_len:
            return

        for i in range(begin_idx, nums_len):
            num = nums[i]

            if num < target:
                temp_result.append(num)
                temp_used_times[num] += 1

                if temp_used_times[num] < nums_times_to_use[num]:
                    next_num_index = i
                else:
                    next_num_index = i + 1
                self.find(nums, nums_len, next_num_index, target - num, results, temp_result, temp_used_times, nums_times_to_use)
                temp_result.pop(-1)
                temp_used_times[num] -= 1
            elif num == target:
                result = temp_result + [num]
                results.append(result)
            elif num > target:
                break

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

        candidates_no_repeat = list()
        nums_times_to_use = dict()
        temp_used_times = dict()
        for candidate in candidates:
            if candidate not in nums_times_to_use:
                nums_times_to_use[candidate] = 1
                temp_used_times[candidate] = 0
                candidates_no_repeat.append(candidate)
            else:
                nums_times_to_use[candidate] += 1

        results, temp_result = list(), list()
        self.find(candidates_no_repeat, len(candidates_no_repeat), 0, target, results, temp_result, temp_used_times, nums_times_to_use)
        return results


solution = Solution()
print(solution.combinationSum2([10, 1, 2, 7, 6, 1, 5], 8))
print(solution.combinationSum2([2, 5, 2, 1, 2], 5))

输出结果

[[1, 1, 6], [1, 2, 5], [1, 7], [2, 6]]
[[1, 2, 2], [5]]

4. 结果

image.png