#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;
}
 

I2luY2x1ZGUgPHN0ZGlvLmg+CiNpbmNsdWRlIDxzdGRsaWIuaD4KCmludCBjID0gMDsKCnZvaWQgZm9vKGNoYXIgKnMxLCBjaGFyICpzMiwgaW50IG4pIHsKCWludCBqOwoJaWYgKCpzMSA9PSAnXDAnKSB7CgkJYysrOwoJCXByaW50ZigiZm9vICUwM2QgJXNcbiIsIGMsIHMyKTsKCX0gZWxzZSB7CgkJZm9yIChqID0gMDsgaiA8IG47IGorKykgewoJCQlpZiAoczJbal0gPT0gJ1wwJykgewoJCQkJczJbal0gPSAqczE7CgkJCQlmb28oczEgKyAxLCBzMiwgbik7CgkJCQlzMltqXSA9ICdcMCc7CgkJCX0KCQl9Cgl9Cn0KCnZvaWQgYmFyKGNoYXIgKnMxLCBjaGFyICpzMiwgaW50IG4pIHsKCWludCAqc3QgPSAoaW50KiljYWxsb2MobiArIDEsIHNpemVvZihpbnQpKTsKCWludCBpLCBqLCBwLCBmLCBjOwoJaSA9IGogPSBwID0gYyA9IDA7CglmID0gMTsKCXdoaWxlIChmKSB7CgkJaWYgKHMyW2pdID09ICdcMCcpIHsKCQkJczJbal0gPSBzMVtpXTsKCQkJaSsrOwoJCQlpZiAoaSA9PSBuKSB7CgkJCQljKys7CgkJCQlwcmludGYoImJhciAlMDNkICVzXG4iLCBjLCBzMik7CgkJCQlzMltqXSA9ICdcMCc7CgkJCQlpLS07CgkJCQlqKys7CgkJCX0gZWxzZSB7CgkJCQlzdFtwXSA9IGo7CgkJCQlwKys7CgkJCQlqID0gMDsKCQkJfQoJCX0gZWxzZSB7CgkJCWorKzsKCQl9CgkJd2hpbGUgKGogPT0gbikgewoJCQlpLS07CgkJCWlmIChpIDwgMCkgewoJCQkJZiA9IDA7CgkJCQlicmVhazsKCQkJfQoJCQlwLS07CgkJCWogPSBzdFtwXTsKCQkJczJbal0gPSAnXDAnOwoJCQlqKys7CgkJfQoJfQoJZnJlZShzdCk7Cn0KCmludCBtYWluKHZvaWQpIHsKCQoJY2hhciBzdHIxW10gPSAiQUJDRCI7CgljaGFyICpzdHIyID0gKGNoYXIqKWNhbGxvYyhzdHJsZW4oc3RyMSkgKyAxLCBzaXplb2YoY2hhcikpOwoJCglmb28oc3RyMSwgc3RyMiwgKGludClzdHJsZW4oc3RyMSkpOwoJYmFyKHN0cjEsIHN0cjIsIChpbnQpc3RybGVuKHN0cjEpKTsKCQoJZnJlZShzdHIyKTsKCQoJcmV0dXJuIDA7Cn0K