Skip to content

Instantly share code, notes, and snippets.

@brenolf
Last active November 13, 2015 01:26
Show Gist options
  • Save brenolf/5775497078a7943bec01 to your computer and use it in GitHub Desktop.
Save brenolf/5775497078a7943bec01 to your computer and use it in GitHub Desktop.
Finds whether or not it is possible to find three elements from three arrays such that they sum up to a given value
#include <stdio.h>
#include <stdlib.h>
#define MAX 100
int a[MAX], b[MAX], c[MAX], n;
int cmp (const void *a, const void *b) {
return *((int*) a) - *((int*) b);
}
void read (int v[MAX]) {
int i;
for (i = 0; i < n; i++)
scanf("%d", &v[i]);
qsort(v, n, sizeof(int), cmp);
}
int find_in_two (int i, int j, int k) {
if (i >= j)
return 0;
int sum = a[i] + b[j];
if (sum == k)
return 1;
if (sum < k)
return find_in_two(i + 1, j, k);
return find_in_two(i, j - 1, k);
}
int find (int k, int i) {
if (i == n)
return 0;
if (find_in_two(0, n - 1, k - c[i]))
return 1;
return find(k, i + 1);
}
int main () {
int k;
while (scanf("%d", &n) != EOF && n != 0) {
scanf("%d", &k);
read(a);
read(b);
read(c);
printf("%c\n", find(k, 0) ? 'S' : 'N');
}
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment