https://leetcode.com/problems/divide-array-in-sets-of-k-consecutive-numbers

leetcode1296.c

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

struct set {
	int n;
	int count;
};

static int
compar(const void *a, const void *b) {
	const int *aa = (const int *)a;
	const int *bb = (const int *)b;
	return *(aa) - *(bb);
}

static int
gen_set(struct set *s, int *nums, int numsSize) {
	qsort(nums, numsSize, sizeof(int), compar);
	int i,j;
	s[0].n = nums[0];
	s[0].count = 1;
	for (i=1,j=0;i<numsSize;i++) {
		if (nums[i] == s[j].n) {
			++s[j].count;
		} else {
			++j;
			s[j].n = nums[i];
			s[j].count = 1;
		}
	}
	return j+1;
}

static bool
possible(struct set *s, int n, int k) {
	if (n < k)
		return false;
    if (s[k-1].n != s[0].n + k -1) {
        return false;
	}
	int i;
	if (n == k) {
		for (i=1;i<k;i++) {
			if (s[i].count != s[0].count)
				return false;
		}
		return true;
	}
	for (i=1;i<k;i++) {
		if ((s[i].count -= s[0].count) < 0)
			return false;
	}
	for (i=1;i<k;i++) {
		if (s[i].count > 0)
			break;
	}    
	return possible(s+i, n-i, k);
}

bool isPossibleDivide(int* nums, int numsSize, int k){
	struct set s[numsSize];
	int count = gen_set(s, nums, numsSize);
	return possible(s, count, k);
}

int
main() {
	int a[] = { 1, 2, 2, 3, 4, 4, 5, 6, 7, 7, 8, 9 };
	bool p = isPossibleDivide(a, sizeof(a)/sizeof(a[0]), 4);
	printf("%s\n", p ? "true" : "false");
	return 0;
};