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

/* Define */
#define ARRAY_MAX   19
#define ARRAY_INPUT { 1, 4, 2, 3, 1, 1, 3, 1, 2, 2, 1, 1, 1, 2, 1, 1, 1, 1, 1 }

#define EXPECT_VAL  5

int array_input[ARRAY_MAX] = ARRAY_INPUT;

/*
 * API find sum combination. This func allow recursion to find
 * all combination from how many elements input.
 */
int find_sum_combination_in_array(int start, int size, int *ele_arr, int ele_num, int expect_val)
{
  int i, j;
  static int lvl = 0;

  for (i = start; i < size; i++) {
    /* Recursion level reach max lelement (0 to (max -1)) allow -> search here, not jump to lower level */
    if (lvl == (ele_num - 1)) {
      if (array_input[i] == expect_val) {
        /* Found combination matching -> print/store. Then continue to find next one */
        ele_arr[lvl] = array_input[i];
        printf("Combination: ");
        for (j = 0; j < ele_num; j++)
          printf("%d ", ele_arr[j]);
        printf("\n");
      }
    /* Recursion level can jump to low level */
    } else {
      ele_arr[lvl] = array_input[i];
      lvl++;
      find_sum_combination_in_array(i + 1, size, ele_arr, ele_num, expect_val - array_input[i]);
    }
  }

  /* Complete at this level, go back higher level to continue new finding. Exit recursion if done first lvl */
  if (lvl != 0)
    lvl--;
  return 0;
}

/* Main func interract with user */
int main(void)
{
  int ele_num;
  int ele_arr[ARRAY_MAX] = { 0 };

  /* Find combination of 2 element */
  ele_num = 2;
  printf("\n");
  memset(ele_arr, 0, ARRAY_MAX * sizeof(int));
  find_sum_combination_in_array(0, ARRAY_MAX, &ele_arr[0], ele_num, EXPECT_VAL);

  ele_num = 3;
  printf("\n");
  memset(ele_arr, 0, ARRAY_MAX * sizeof(int));
  find_sum_combination_in_array(0, ARRAY_MAX, &ele_arr[0], ele_num, EXPECT_VAL);

  return 0;
}

/*
vector<vector<int>> print_all_sum(int target){
    vector<vector<int>> output;
    //Write - Your - Code
    return output;
}
*/