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

一、题目

题目描述：

给定一个整数数组 nums、一个数字k，一个整数目标值 target，请问nums中是否存在k个元素使得其相加结果为target，请输出所有符合条件且不重复的k元组的个数
数据范围 2 <= nums.length <= 200 -10^9 < numslil <?10^9 -10^9 <?target <?10^9 2<=k<=100

二、输入输出

输入描述:
第一行是nums取值: 2 7 11 15?
第二行是k的取值: 2?
第三行是target取值: 9
输出描述:
输出第一行是符合要求的元组个数: 1
补充说明: [2,7]满足，输出个数是1

三、示例

示例1：
输入：
-1 0 1 2 -1 -4
3
0?
输出：
2?
说明：
?[-1,0,1]，[-1,-1,2]满足条件

五、解题思路

直接遍历所有可能性

六、参考代码?

# -*- 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)