"""
给定一个数组 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]
]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/combination-sum-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
"""

# 这个题我做的时候把index搞错了好久，值得注意下
from typing import *
import copy


def combinationSum2(candidates: List[int], target: int) -> List[List[int]]:
    def dfs(candidates, target, combines, marks, index):
        if target == 0:
            return [combines]
        elif target < 0:
            return []

        all_combines = []
        for i in range(index, len(candidates)):
            k = candidates[i]
            if marks[k] > 0:
                marks[k] -= 1
                next_combine = copy.copy(combines)
                next_combine.append(k)
                if marks[k] <= 0:
                    to_extend = dfs(candidates, target - candidates[i], next_combine, marks, i+1)
                else:
                    to_extend = dfs(candidates, target - candidates[i], next_combine, marks, i)
                all_combines.extend(to_extend)
                marks[k] += 1
        return all_combines

    marks = dict()
    for key in candidates:
        marks[key] = marks.get(key, 0) + 1
    candidates = list(set(candidates))
    return dfs(candidates, target, [], marks, 0)


if __name__ == '__main__':
    print(combinationSum2([10,1,2,7,6,1,5], 8))
