华为机试【求符合条件元组个数】
给定一个整数数组 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
#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
#include<string.h>
//在数组中取k个数，等于target，有多少种取法，输出结果
int A[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
int k = 5;
int target = 25;
const int max = 15;
int** result = (int**)malloc(sizeof(int*)*max);
int resultcount = 0;
int *path = (int*)malloc(sizeof(int)*k);
int pathCount = 0;
void printF()
{
for (int i = 0; i < max; i++)
{
for (int j = 0; j < k; j++)
{
printf("%d", result[i][j]);
}
printf("\n");
}
}
bool cmp(int*A, int*B,int num)
{
for (int i = 0; i < num; i++)
{
if (A[i] != B[i]){
return false;
}
}
return true;
}
void put(int* path)
{
int sum = 0;
for (int i = 0; i < k; i++)
{
sum += path[i];
}
if (sum != target)
{
return;
}
bool iscontain = false;
//if result contain path :skip
for (int i = 0; i < resultcount; i++)
{
if (cmp(result[resultcount], path, k))
{
iscontain = true;
break;
}
}
if (!iscontain)
{
memcpy(result[resultcount++], path, sizeof(int)*k);
printF();
}
}
void back(int startIndx)
{
if (pathCount == k)
{
put(path);
return;
}
for (int i = startIndx; i < sizeof(A)/sizeof(A[0]); i++)
{
path[pathCount++] = A[i];
back(i + 1);
pathCount--;
}
}
int main()
{
for (int i = 0; i < max; i++)
{
result[i] = (int*)malloc(sizeof(int)*k);
}
back(0);
return 0;
}
