main.c

// can't find the source but made this because there was a discussion 
// online where many people claimed that if you have two arrays the minimum
// time complexity you can get to find all common sub-sums is around O(2^n)

#include <stdlib.h>

#include <stdio.h>

#include <assert.h>

#define NO_SOL    -2

#define EMPTY_SOL -1

typedef struct Solution {

        int index;

        struct Solution *added;

        struct Solution *prev;

} sl;

unsigned int sum(unsigned int list[], unsigned int size) {

        unsigned int result = 0;

        for (unsigned int i = 0; i < size; i++) {

                result += list[i];

        }

        return result;

}

sl *make_sl(int index, sl *added, sl *prev) {

        sl *new_sl = malloc(sizeof(sl)); // could save time by allocating ahead

        if (!added || added->index != NO_SOL) {

                new_sl->added = added;

        } else {

                return prev;

        }

        if (!prev || prev->index != NO_SOL) {

                new_sl->prev = prev;

        } else {

                new_sl->prev = NULL;

        }

        new_sl->index = index;

        return new_sl;

}

sl *shared_sum(unsigned int list1[], unsigned int size1, unsigned int list2[], unsigned int size2) {

        /**

        Takes O(min(sum(list1), sum(list2)) * (size1 + size2)) time

        Takes two lists and their sizes and returns a solution binary tree where the `added` branch means you need to add the value corresponding to the `index` of the parent node and the `prev` branch means you can get a solution without adding it

        The function excpects the first list to have a lower sum

        Indexes samaller than `size1` will be treated as `list1` indexes, and others will be treated as the `index - size1` index of list2

        The solution satisfies that for the needed indexes the subsum of list1 plus the subsum of list2 is equal to the sum of list1

        The solution also is gurenteed not to be the range from 0 to `size1`

        From these propeties we can see that if we want to get a non-empty subsum of `list1` that equals a subsum of `list2` we can take the indexes of `list1` that are **not needed** for the solution with the indexes of `list2` that **are** needed

        That is true because both the unneeded `list1` indexes and the needed `list2` indexes will complete the needed `list1` indexes subsum to the sum of `list1` so they are equal

        */

        unsigned int sum1 = sum(list1, size1);

        assert(sum1 <= sum(list2, size2));

        sl **sums = malloc((sum1 + 1) * sizeof(sl*));

        sums[0] = make_sl(EMPTY_SOL, NULL, NULL);

        for (unsigned int i = 1; i <= sum1; i++) {

                sums[i] = make_sl(NO_SOL, NULL, NULL);

        }

        for (unsigned int i = 0; i < size1; i++) {

                for (unsigned int j = sum1 - 1; j >= list1[i]; j--) {

                        sums[j] = make_sl(i, sums[j - list1[i]], sums[j]);

                }

        }

        for (unsigned int i = 0; i < size2; i++) {

                for (unsigned int j = sum1; j >= list2[i]; j--) {

                        sums[j] = make_sl(i + size1, sums[j - list2[i]], sums[j]);

                }

        }

        return sums[sum1];

}

void traverse_step(int16_t **cur_pointer, sl *node, int16_t cur_path, char depth) {

        if (!node->added && !node->prev) {

                **cur_pointer = cur_path;

                (*cur_pointer)++;

        }

        if (node->prev) {

                traverse_step(cur_pointer, node->prev, cur_path, depth + 1);

        }

        if (node->added) {

                traverse_step(cur_pointer, node->added, cur_path | (1<<depth), depth + 1);

        }

}

void print_solution(sl *sol, unsigned int list1[], unsigned int size1, unsigned int list2[]) {

        // for simplicity I'll assume tree depth of 16 max

        // this is guaranteed if the combined length of list1 and list2 is 16 or less

        // otherwise we'll have to do recursion or something because saving the traversals will be costly

        if (sol->index == NO_SOL) {

                printf("No solutions found\n");

                return;

        }

        int16_t traversals[1<<16] = {};

        int16_t *copy = traversals;

        traverse_step(&copy, sol, 0, 0);

        int16_t traversal;

        for (unsigned int i = 0; (traversal = traversals[i]) || !i; i++) {

                int16_t indexes = (1<<size1) - 1;

                sl *sol_copy = sol;

                for (unsigned int j = 0; j < 16; j++) {

                        if ((traversal>>j) & 1) {

                                indexes ^= (1<<(sol_copy->index));

                                sol_copy = sol_copy->added;

                        } else {

                                if (sol_copy->prev) {

                                        sol_copy = sol_copy->prev;

                                } else {

                                        indexes ^= (1<<(sol_copy->index));

                                        break;

                                }

                        }

                }

                printf("Solution #%d\n", i + 1);

                unsigned int sum = 0;

                for (unsigned int j = 0; j < 16; j++) {

                        if ((indexes>>j) & 1) {

                                if (j < size1) {

                                        sum += list1[j];

                                        printf("list1[%d]=%d\n", j, list1[j]);

                                } else {

                                        printf("list2[%d]=%d\n", j - size1, list2[j - size1]);

                                }

                        }

                }

                printf("Both sums to: %d\n\n", sum);

        }

}

int main() {

        unsigned int list2[] = {4, 4, 1};

        unsigned int list1[] = {1, 2, 5};

        unsigned int size1 = sizeof(list1) / sizeof(list1[0]);

        unsigned int size2 = sizeof(list2) / sizeof(list2[0]);

        sl *solution = shared_sum(list1, size1, list2, size2);

        print_solution(solution, list1, size1, list2);

}