2023年华为OD机试（python）B卷-符合要求的元组的个数-K数之和

一、题目

二、输入输出

三、示例

五、解题思路

六、参考代码 

# -*- coding: utf-8 -*-
'''
@File    :   2023-B-符合要求的元组的个数-K数之和.py
@Time    :   2023/12/28 01:14:28
@Author  :   mgc 
@Version :   1.0
@Desc    :   None
'''

# import os
# import re
# import sys
# import copy
# import math
# import queue
# import functools
# from queue import Queue
# from collections import Counter, defaultdict

def countKSum(nums, k, target):
    nums = sorted(nums)  # 对数组进行升序排序

    result = 0  # 计数器，用于记录符合条件的k元组的个数

    def dfs(pos, sum_val, count):
        nonlocal result

        if count == k and sum_val == target:  # 当已选择的元素个数等于k且总和等于target时，找到一个符合条件的k元组
            result += 1
            return

        i = pos
        while i < len(nums):
            if i > pos and nums[i - 1] == nums[i]:
                i += 1
                continue

            if count + 1 == k:
                if sum_val + nums[i] == target:
                    result += 1
                # 不满足条件时不需要进行额外操作，直接跳过即可

            else:
                new_pos = i + 1
                dfs(new_pos, sum_val + nums[i], count + 1)

            i += 1

    dfs(0, 0, 0)

    return result


# 测试代码
nums = [int(x) for x in input().split(" ")]  # 整数数组nums
k = int(input())  # k的取值
target = int(input())  # 目标值target

result = countKSum(nums, k, target)
print(result)