/* Include lib */
#include <stdio.h>
#include <assert.h>

/* Define */
#define ARRAY_MAX   7
#define ARRAY_INPUT { 3, 7, 1, 2, 8, 4, 5 }

#define EXPECT_VAL  21

int array_input[ARRAY_MAX] = ARRAY_INPUT;

/* API find sum combination of 3 element */
int find_sum_of_3_elements(int *arr, int arr_size, int expect_val)
{
  int i, j, k, l = 0;

  /* TODO: Check input pointer, size */

  /* Start with 1st element, find all combination contain it */
  for (i = 0; i < arr_size; i++) {
    /* Cont. with 2nd element, find all combination contain it */
    for (j = (i + 1); j < arr_size; j++) {
      /* Cont. with 3rd element, find all combination contain it */
      for (k = (j + 1); k < arr_size; k++) {
        if ((arr[i] + arr[j] + arr[k]) == expect_val) {
          printf("\nCombination %d\n", l++);
          printf("a [index %d] = %d\n", i, arr[i]);
          printf("b [index %d] = %d\n", j, arr[j]);
          printf("c [index %d] = %d\n", k, arr[k]);
        }
      }
    }
  }

  if (l == 0) {
    printf("\nNO Combination\n");
    return -1;
  }

  return 0;
}

/* Main func interract with user */
int main(void)
{
  int i;

  printf("Input array: ");
  for (i = 0; i < ARRAY_MAX; i++)
    printf("%d ", array_input[i]);
  printf("\n");

  /* Find combinations of 3 elements */
  find_sum_of_3_elements(&array_input[0], ARRAY_MAX, EXPECT_VAL);

  return 0;
}

/*
bool find_sum_of_three(vector<int> arr,
  int required_sum) {
  // TODO: Write - Your - Code

  return false;
}
*/



#if 0
/* Include lib */
#include <stdio.h>
#include <assert.h>
#include <string.h>

/* Define */
#define ARRAY_INPUT   { 3, 7, 1, 2, 8, 4, 5 }
#define ARRAY_MAX     7
#define EXPECT_VAL    20

int array_input[ARRAY_MAX] = ARRAY_INPUT;

struct element {
  int index;
  int val;
};

/* API find sum combination of 2 element */
int find_sum_2_elements(int *arr, int arr_size, int expect_val,
                        struct element *ret_a, struct element *ret_b)
{
  int i, j;

  /* TODO: check pointer input */

  for (i = 0; i < arr_size; i++) {
    for (j = 0; j < arr_size; j++) {
      if ((i != j) && ((arr[i] + arr[j]) == expect_val)) {
        ret_a->index = i;
        ret_a->val = arr[i];
        ret_b->index = j;
        ret_b->val = arr[j];

        return 0;
      }
    }
  }

  return -1;
}

/* API find sum combination of 3 element */
int find_sum_3_elements(int *arr, int arr_size, int expect_val,
                        struct element *ret_a, struct element *ret_b,
                        struct element *ret_c)
{
  int i, j, k;
  int ret;
  int array_tmp[ARRAY_MAX - 1] = { 0 };

  /* TODO: Check pointer input */

  for (i = 0; i < arr_size; i++) {
    /* With each element i, search 2 combination in new array from array input, except element i */
    k = 0;
    memset(&array_tmp[0], 0, sizeof(int) * (ARRAY_MAX - 1));
    for (j = 0; j < arr_size; j++) {
      if (i != j)
        array_tmp[k++] = arr[j];
    }

    /* Search 2 combination */
    ret = find_sum_2_elements(&array_tmp[0], ARRAY_MAX - 1, expect_val - arr[i],
                              ret_b, ret_c);
    if (!ret) {
      ret_a->index = i;
      ret_a->val = arr[i];
      return 0;
    }
  }

  return -1;
}

/* Main func interract with user */
int main(void) 
{
  int i;
  struct element a, b, c;

  printf("Input array: ");
  for (i = 0; i < ARRAY_MAX; i++) {
    printf("%d ", array_input[i]);
  }
  printf("\n");

  /* Find combination 3 elements */
  if (find_sum_3_elements(&array_input[0], ARRAY_MAX, EXPECT_VAL, &a, &b, &c)) {
    printf("Cannot find any combination matching %d !!\n", EXPECT_VAL);
  } else {
    printf("a [index %d] = %d\n", a.index, a.val);
    printf("b [index %d] = %d\n", b.index, b.val);
    printf("c [index %d] = %d\n", c.index, c.val);

    /* TODO: Find diff combinations giving same result */ 
  }

  return 0;
}

/*
bool find_sum_of_three(vector<int> arr,
  int required_sum) {
  // TODO: Write - Your - Code

  return false;
}
*/
#endif