如何改进函数：判断元素集合能否生成目标并返回正确已用资源

问题背景 #

现有字典product_dict存储元素及其子元素关系：

product_dict = {
    'A': {'B', 'C', 'D'},
    'B': {'E', 'F'},
    'C': {'G'},
    'E': {'H', 'I'}
}

根据该字典的生成规则：

• B、C、D可生成A；
• E、F、G、D可生成A；
• H、I、F、G、D可生成A；
• D无法被生成（无对应子元素）。

需求是实现一个函数，判断给定资源集合能否组合生成目标元素，同时返回生成目标实际用到的资源列表（排除无关资源）；若资源不足无法生成目标，则返回空列表。

现有函数存在缺陷：当目标为B、资源仅为F和G时，函数返回[F]，但实际缺少E无法生成B，应返回空列表。

改进后的函数实现 #

def can_create(target, resources, product_dict):
    # 将资源转为集合，提升查找效率
    resource_set = set(resources)
    used = set()

    def helper(current_target):
        # 当前目标直接在资源中，标记使用并返回成功
        if current_target in resource_set:
            used.add(current_target)
            return True
        
        # 当前目标无生成规则，无法生成
        if current_target not in product_dict:
            return False
        
        # 遍历所有子元素，必须全部能生成才算满足条件
        for child in product_dict[current_target]:
            if not helper(child):
                return False
        
        return True
    
    # 若能生成目标则返回已用资源列表，否则返回空
    if helper(target):
        return list(used)
    else:
        return []

关键改进点说明 #

1. 集合优化操作：用集合存储资源和已用项，既提升查找速度，又自动避免重复记录同一资源。
2. 严格依赖校验：递归检查子元素时，只要有一个子元素无法生成，直接返回失败，确保所有生成依赖都被满足。
3. 逻辑与状态分离：通过内部辅助函数helper处理递归逻辑，同时维护used集合记录实际消耗的资源，避免全局状态干扰。
4. 清晰的分支返回：仅当所有依赖都满足时返回已用资源列表，否则直接返回空列表，结果符合预期逻辑。

测试示例 #

• 测试目标B，资源为['E', 'F', 'G']：

  print(can_create('B', ['E', 'F', 'G'], product_dict))  # 输出: ['E', 'F']
  

• 测试目标B，资源为['F', 'G']：

  print(can_create('B', ['F', 'G'], product_dict))  # 输出: []
  

• 测试目标A，资源为['H', 'I', 'F', 'G', 'D']：

  print(can_create('A', ['H', 'I', 'F', 'G', 'D'], product_dict))  # 输出: ['H', 'I', 'F', 'G', 'D']
  

内容的提问来源于stack exchange，提问作者Frederico Portela