华为机试【求符合条件元组个数】

给定一个整数数组 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;

}