add_chain_0.c

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

uintmax_t calls;

void print(int *chain, int len)
{
    for (int i = 0; i < len; i++)
        printf("%d,", chain[i]);
    printf("\n%"PRIuMAX" calls\n", calls);
}

int solve(int *chain, int len, int depth, int goal)
{
    calls++;

    if (depth + 1 == len && chain[depth] == goal) {
        print(chain, len);
        return 1;
    }
    if (depth + 1 == len || chain[depth] > goal)
        return 0;
    for (int i = 0; i <= depth; i++) {
        chain[depth + 1] = chain[depth] + chain[i];
        if (solve(chain, len, depth + 1, goal))
            return 1;
    }
    return 0;
}

int main(int argc, char **argv)
{
    if (argc != 3)
        return 1;

    int len = atoi(argv[1]), goal = atoi(argv[2]);
    int chain[len + 1];
    chain[0] = 1;
    return !solve(chain, len + 1, 0, goal);
}

add_chain_1.c

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

uintmax_t calls;

void print(int *chain, int len)
{
    for (int i = 0; i < len; i++)
        printf("%d,", chain[i]);
    printf("\n%"PRIuMAX" calls\n", calls);
}

int solve(int *chain, int len, int depth, int goal)
{
    calls++;

    if (depth + 1 == len && chain[depth] == goal) {
        print(chain, len);
        return 1;
    }
    if (depth == len ||
        chain[depth] * (1 << len - depth) < goal ||
        chain[depth] > goal)
        return 0;
    for (int i = 0; i <= depth; i++) {
        chain[depth + 1] = chain[depth] + chain[i];
        if (solve(chain, len, depth + 1, goal))
            return 1;
    }
    return 0;
}

int main(int argc, char **argv)
{
    if (argc != 3)
        return 1;

    int len = atoi(argv[1]), goal = atoi(argv[2]);
    int chain[len + 1];
    chain[0] = 1;
    return !solve(chain, len + 1, 0, goal);
}

add_chain_2.c

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

uintmax_t calls;

void print(int *chain, int len)
{
    for (int i = 0; i < len; i++)
        printf("%d,", chain[i]);
    printf("\n%"PRIuMAX" calls\n", calls);
}

int solve(int *chain, int len, int depth, int goal)
{
    calls++;

    if (depth + 1 == len && chain[depth] == goal) {
        print(chain, len);
        return 1;
    }
    if (chain[depth] * (1 << len - depth) < goal ||
        chain[depth] > goal ||
        depth + 1 == len)
        return 0;
    for (int i = depth; i >= 0; i--) {
        chain[depth + 1] = chain[depth] + chain[i];
        if (solve(chain, len, depth + 1, goal))
            return 1;
    }
    return 0;
}

int main(int argc, char **argv)
{
    if (argc != 3)
        return 1;

    int len = atoi(argv[1]), goal = atoi(argv[2]);
    int chain[len + 1];
    chain[0] = 1;
    return !solve(chain, len + 1, 0, goal);
}