#include <stdio.h>
#include <math.h> // pow
#include <stdlib.h> // atoi, malloc

void ten_to_bin(int count, int x, char *mask) {
  int i = 0;
  while (x != 0 && i < count) {
    // Превращаем 0 в '0' (код 48), 1 в '1' (код 49)
    mask[i] = (x % 2) + '0';
    mask[i+1] = '\0';
    x /= 2;
    i++;
  }
}

int calculate_sum(int count, int *numbers, char *mask) {
  int x = 0;
  for (int i = 0; mask[i] != '\0' && i < count; i++) {
    if (mask[i] == '1') {
      x += numbers[i];
    }
  }
  return x;
}

void find_sum(int count, long long target, int *numbers, char *mask) {
  long long total_combinations = pow(2, count) - 1;
  printf("Total combinations: %lld\n", total_combinations);

  for (int i = 0; i <= total_combinations; i++) {
    ten_to_bin(count, i, mask);
    long long current_sum = calculate_sum(count, numbers, mask);

    if (current_sum == target) {
      // Печать результата
      printf("OK: %s\n", mask);
      return;
    }
  }
  printf("NO: not found.\n");
}

int main(int argc, char *argv[]) {
  // 1. Валидация ввода
  if (argc < 5) {
    printf("ER: input parameters \n");
    return 1;
  }

  if (argc > 30) {
    printf("ER: input parameters \n");
    return 1;
  }

  // 2. Формирование массива int
  long long target = atoi(argv[1]);    // Требуемая сумма
  int count = argc - 2;                // Количество переданных чисел
  int *numbers = malloc(count * sizeof(int));  // Mассив чисел

  for (int i = 0; i < count; i++) {
    // Преобразуем каждый аргумент (начиная с argv[2]) в int
    numbers[i] = atoi(argv[i + 2]);
  }

  // 3. Формирование массива char
  // +1 для символа конца строки  '\0'
  char *mask = calloc(count + 1, sizeof(char));

  // 4. Данные готовы, начинаем считать
  find_sum(count, target, numbers, mask);

  // 5. Освобождаем память
  free(mask);
  free(numbers);
  return 0;
}