#include <stdio.h>
#include <stdlib.h>

int do_findArrayQuadruplet(int *arr, int *out, size_t arrLength, int s, int i, int j, int k, int l)
{
  int sum, ret = 0;

  if (arrLength < 4)
    return 0;

  if (!arr || !out)
    return 0;

  sum = arr[i]+arr[j]+arr[k]+arr[l];

  if (sum == s) { // Sort out
    out[0] = arr[i];
    out[1] = arr[j];
    out[2] = arr[k];
    out[3] = arr[l];
    return 1;
  }

  if (i < arrLength)
    ret = do_findArrayQuadruplet(arr, out, arrLength, s, i+1, j, k, l); // i, j, k, l

  if (!ret && j < arrLength)
    ret = do_findArrayQuadruplet(arr, out, arrLength, s, i, j+1, k, l);

  if (!ret && k < arrLength)
    ret = do_findArrayQuadruplet(arr, out, arrLength, s, i, j, k+1, l);

  if (!ret && l < arrLength)
    ret = do_findArrayQuadruplet(arr, out, arrLength, s, i, j, k, l+1);

  return ret;
}

void findArrayQuadruplet(int const *arr, int* out, size_t arrLength, int s) {
  // your code goes here
/*
take first 4 no check if sum is s
  idx_1, idx_2 , idx_3 idx_4
*/
  if (arrLength < 4)
    return;

  if (!arr || !out)
    return;

  if (do_findArrayQuadruplet(arr, out, arrLength, s, 0, 1, 2, 3))
    sort(out, 4);
}

int main() {
  return 0;
}

// sort the array ascending order
sort(arr);

  // four for loops -> O(n^3)  -> brute force first two numbers, first <= second
  // last two numbers with given sum, 4sum - first two number's
  // two sum -> two pointer technique , line 27 spent O(n^2), line 28, O(n), in total O(n^3)
  // 1, 2, 3, 4, 5, 6, 7, 8, 9
  // find two numbers with given 11,
  // 1, 9 = 10 < 11
  // 1 -> 2, 9 = 11 > 10
  for(int i = 0; i < len; i++)
    for(int j = i + 1; j < len; j++)
      for(int k = j + 1; k < len; k++)
        for(int l = k + 1; l < len; l++)