【华为OD-E卷 - 求符合条件元组个数 100分（python、java、c++、js、c）】
题目
给定一个整数数组 nums、一个数字k，一个整数目标值 target，请问nums中是否存在k个元素使得其相加结果为target，请输出所有符合条件且不重复的k元组的个数
数据范围
2 ≤ nums.length ≤ 200 -10^9 ≤ nums[i] ≤ 10^9 -10^9 ≤ target ≤ 10^9 2 ≤ k ≤ 100
输入描述
- 第一行是nums取值：2 7 11 15
第二行是k的取值：2
第三行是target取值：9
输出描述
- 输出第一行是符合要求的元组个数：1
补充说明：[2,7]满足，输出个数是1
用例
用例一：
输入：
-1 0 1 2 -1 -4
3
0
输出：
2
用例二：
输入：
2 7 11 15
2
9
输出：
1
python解法
- 解题思路：
- 输入解析：
首先，从标准输入读取一行整数，并转换为 nums 列表。
读取 k 作为组合的大小。
读取 target 作为目标和。
排序：
将 nums 进行排序，以便后续生成组合时按序排列，方便去重。
使用 combinations 生成所有可能的 k 元素组合：
Python 内置的 itertools.combinations() 函数可以直接生成 k 个元素的所有可能的无重复组合。
计算和进行筛选：
遍历所有 k 元素组合，检查其元素之和是否等于 target。
使用 set() 存储符合条件的组合，保证去重（combinations 本身生成的组合是无序的，但 set 可以避免重复存储相同的组合）。
返回符合条件的组合个数：
计算 result 的长度并返回，即满足 sum(comb) == target 的组合数量。
使用到的算法
组合生成算法 (combinations)：
itertools.combinations() 生成所有长度为 k 的组合，时间复杂度为 O(C(n,k))，即 O(n! / (k!(n-k)!))。
排序 (sort())：
采用 O(n log n) 的排序算法（Timsort）。
集合去重 (set)：
插入操作平均复杂度是 O(1)，但整体去重依赖组合生成的结果
from itertools import combinations # 导入组合生成函数
# 读取输入数据
nums = list(map(int, input().split())) # 输入多个整数并转换为列表
k = int(input()) # 读取整数 k，表示选取的元素个数
target = int(input()) # 读取目标和 target
def getResult():
nums.sort() # 先对 nums 进行排序，确保组合是按序排列
result = set() # 使用 set 存储符合条件的组合，去重
# 遍历所有可能的 k 元素组合
for comb in combinations(nums, k):
if sum(comb) == target: # 计算当前组合的和，是否等于 target
result.add(comb) # 满足条件的组合添加到集合中
return len(result) # 返回符合条件的组合个数
print(getResult()) # 调用函数并输出结果
java解法
- 解题思路
- 读取输入数据：
读取第一行的整数数组 numbers。
读取 elementCount 作为目标组合的元素个数。
读取 targetValue 作为目标和。
排序：
先对 numbers 进行排序，这有助于后续去重，并且在优化 two-pointer 方法时有帮助。
递归回溯寻找组合：
通过 findCombinations() 递归遍历 numbers，寻找所有 elementCount 个元素的组合，使其总和等于 targetValue。
递归过程中，避免选择相同的元素（通过 i > startIndex && numbers[i] == numbers[i - 1] 跳过重复元素）。
两数之和优化：
当 elementCount - currentCount == 2 时，说明还需要两个元素来满足 elementCount，可以使用 双指针法 来寻找两个数之和等于 targetValue - currentSum 的情况，从而减少时间复杂度。
计数：
使用 resultCount 记录所有符合要求的组合数。
使用到的算法
回溯算法（Backtracking）：
用于生成所有可能的 k 元素组合，进行递归搜索。
排序（Sorting）：
先对 numbers 进行排序，便于去重（O(n log n)）。
双指针（Two-Pointer Search）：
在 k=2 的情况下使用双指针进行快速查找，降低复杂度
import java.util.Arrays;
import java.util.Scanner;
public class Main {
private static int[] numbers; // 存储输入的数组
private static int targetValue; // 目标和
private static int elementCount;// 目标组合元素个数
private static int resultCount = 0; // 记录符合条件的组合数
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
// 读取输入数据
numbers = Arrays.stream(scanner.nextLine().split(" ")) // 读取一行数据并转换成整数数组
.mapToInt(Integer::parseInt)
.toArray();
elementCount = Integer.parseInt(scanner.nextLine()); // 读取目标组合的元素个数
targetValue = Integer.parseInt(scanner.nextLine()); // 读取目标和
System.out.println(findKSumCombinations()); // 计算并输出符合条件的组合数量
}
/**
* 计算符合目标和的 k 组合的数量
*/
private static int findKSumCombinations() {
Arrays.sort(numbers); // 先对数组排序，便于去重及优化搜索
findCombinations(0, 0, 0); // 递归回溯寻找组合
return resultCount;
}
/**
* 递归回溯查找符合条件的组合
*
* @param startIndex 当前搜索起始索引
* @param currentSum 当前选中元素的总和
* @param currentCount 当前选中的元素个数
*/
private static void findCombinations(int startIndex, long currentSum, int currentCount) {
// 递归终止条件：当选中元素个数达到目标值
if (currentCount == elementCount) {
if (currentSum == targetValue) { // 如果总和匹配目标值，则增加计数
resultCount++;
}
return;
}
// 当还剩 2 个元素未选择时，使用双指针方法加速查找
if (currentCount == elementCount - 2) {
twoPointerSearch(startIndex, currentSum);
return;
}
// 继续递归选择元素
for (int i = startIndex; i < numbers.length; i++) {
// 跳过重复元素，避免重复组合
if (i > startIndex && numbers[i] == numbers[i - 1]) continue;
// 递归查找下一层
findCombinations(i + 1, currentSum + numbers[i], currentCount + 1);
}
}
/**
* 使用双指针方法寻找两个数，使其总和加上 currentSum 等于 targetValue
*
* @param startIndex 当前起始索引
* @param currentSum 当前已选元素的总和
*/
private static void twoPointerSearch(int startIndex, long currentSum) {
int left = startIndex, right = numbers.length - 1;
while (left < right) {
long sum = currentSum + numbers[left] + numbers[right];
if (sum == targetValue) {
resultCount++; // 找到一个符合的组合
left++;
right--;
// 跳过相同元素，避免重复组合
while (left < right && numbers[left] == numbers[left - 1]) left++;
while (left < right && numbers[right] == numbers[right + 1]) right--;
} else if (sum < targetValue) {
left++; // 总和过小，增加左指针
} else {
right--; // 总和过大，减少右指针
}
}
}
}
C++解法
- 解题思路
- 输入解析：
从标准输入 cin 读取整数，存入 vector arr。
读取 q（组合中元素的个数）。
读取 aim（目标和）。
排序：
先对 arr 进行排序，以便后续搜索时进行去重，减少不必要的递归分支。
回溯搜索：
递归函数 search(idx, sum, cnt) 负责从 idx 开始，选择 q 个元素，使其总和等于 aim。
递归终止条件：当 cnt == q，检查 sum 是否等于 aim，如果满足条件，则 res++。
剪枝：若当前元素与前一个元素相同，则跳过，防止重复组合。
计算符合条件的组合数量：
递归搜索所有可能的 q 元素组合，最终返回 res 作为符合条件的组合数。
使用到的算法
回溯算法（Backtracking）：
通过递归尝试所有可能的 q 组合，并进行剪枝优化，避免重复计算。
排序（Sorting）：
先对 arr 进行排序，便于去重和优化搜索
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
class CombinationFinder {
private:
vector<int> arr; // 存储输入数组
int aim; // 目标和
int q; // 目标组合的元素个数
int res; // 记录符合条件的组合数
/**
* 递归搜索符合条件的组合
* @param idx 当前搜索的起始索引
* @param sum 当前组合的总和
* @param cnt 当前已选中的元素个数
*/
void search(int idx, long sum, int cnt) {
// 当选择的元素达到 q 个时，检查是否满足目标和
if (cnt == q) {
if (sum == aim) {
res++; // 找到一个符合条件的组合
}
return;
}
// 遍历所有可能的元素
for (int i = idx; i < arr.size(); i++) {
// 跳过重复元素，避免重复计算
if (i > idx && arr[i] == arr[i - 1]) {
continue;
}
// 递归搜索下一层
search(i + 1, sum + arr[i], cnt + 1);
}
}
public:
/**
* 构造函数，初始化数据并排序
* @param inputArr 输入数组
* @param k 目标组合元素个数
* @param target 目标和
*/
CombinationFinder(vector<int> inputArr, int k, int target) : arr(inputArr), q(k), aim(target), res(0) {
sort(arr.begin(), arr.end()); // 排序以便去重
}
/**
* 启动搜索并返回结果
*/
int getResult() {
search(0, 0, 0);
return res;
}
};
int main() {
vector<int> arr; // 存储输入的数组
int val;
// 读取数组输入，直到换行结束
while (cin >> val) {
arr.push_back(val);
if (cin.peek() == '\n') break; // 遇到换行符结束输入
}
int q;
cin >> q; // 读取目标组合的元素个数
int aim;
cin >> aim; // 读取目标和
// 创建 CombinationFinder 实例并计算符合条件的组合数
CombinationFinder finder(arr, q, aim);
cout << finder.getResult() << endl;
return 0;
}
C解法
更新中
JS解法
更新中
注意：
如果发现代码有用例覆盖不到的情况，欢迎反馈！会在第一时间修正，更新。
解题不易，如对您有帮助，欢迎点赞/收藏