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

int c = 0;

void foo(char *s1, char *s2, int n) {
	int j;
	if (*s1 == '\0') {
		c++;
		printf("foo %03d %s\n", c, s2);
	} else {
		for (j = 0; j < n; j++) {
			if (s2[j] == '\0') {
				s2[j] = *s1;
				foo(s1 + 1, s2, n);
				s2[j] = '\0';
			}
		}
	}
}

void bar(char *s1, char *s2, int n) {
	int *st = (int*)calloc(n + 1, sizeof(int));
	int i, j, p, f, c;
	i = j = p = c = 0;
	f = 1;
	while (f) {
		if (s2[j] == '\0') {
			s2[j] = s1[i];
			i++;
			if (i == n) {
				c++;
				printf("bar %03d %s\n", c, s2);
				s2[j] = '\0';
				i--;
				j++;
			} else {
				st[p] = j;
				p++;
				j = 0;
			}
		} else {
			j++;
		}
		while (j == n) {
			i--;
			if (i < 0) {
				f = 0;
				break;
			}
			p--;
			j = st[p];
			s2[j] = '\0';
			j++;
		}
	}
	free(st);
}

int main(void) {
	
	char str1[] = "ABCD";
	char *str2 = (char*)calloc(strlen(str1) + 1, sizeof(char));
	
	foo(str1, str2, (int)strlen(str1));
	bar(str1, str2, (int)strlen(str1));
	
	free(str2);
	
	return 0;
}