Algorithms: To determine whether a given set has two subsets which are disjoint such that sum of elements in both subsets is same?

Question

Here is the code that I have written:-

#include 
#include 
#include 

int ctr = 0;

void partition(int arr[], int n) {
    int i, j, k = 0, r, in = 0, te, flag = 0;
    int *sum;
    sum = (int*)malloc(sizeof(int) * pow(2, n));
    for (i = 0; i < pow(2, n); i++) {
        printf("{");
        for (j = 0; j < n; j++) {
            if (i & (1 << j)) {
                printf("%d ", arr[j]);
                sum[k] = sum[k] + arr[j];
            }
        }
        k++;
        printf("}");
        printf("
");
    }
    printf("
 
");

    int *temp;
    for (k = 0; k < pow(2, n) - 1; k++) {
        in = 0;
        temp = (int*)malloc(sizeof(int));
        for (r = k + 1; r < pow(2, n); r++) {
            if (sum[k] == sum[r]) {
                printf("
 Printing solution for sum %d", sum[k]);
                for (i = 0; i < pow(2, n); i++) {
                    if (i == k || i == r) {
                        printf("{");
                        for (j = 0; j < n; j++) {
                            if (i & 1 << j) {
                                for (te = 0; te < in; te++) { //Disjointness
                                    if (temp[te] == arr[j])
                                        flag = 1;
                                }
                                if (flag == 1)
                                    break;
                                temp[in++] = arr[j];
                                temp = (int*)realloc(temp, sizeof(int));
                                printf("%d ", arr[j]);
                            }
                        }
                        printf("}");
                        printf("
");
                    }
                }
                break;          
            }
        }
        free(temp);
    }
}

void main() {
    int *arr, n, i;
    printf("
 Enter the number of elements in the set 
");
    scanf("%d", &n);
    arr = (int*)malloc(sizeof(int) * n);
    printf("
 Enter the set elements 
");
    for (i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
    }
    partition(arr, n);
}

It works perfectly for the input {1,2,3}. For {1,2,3,4}, it gives the correct output as well.

For {1,2,3,4}, the output is:

Printing solution for sum 3{1 2 }
{3 }

 Printing solution for sum 4{1 3 }
{4 }

 Printing solution for sum 5{2 3 }
{1 4 }

 Printing solution for sum 6{1 2 3 }
{}

 Printing solution for sum 7{}
{}

But if the input is {1,5,11,5}, the output is:

 Printing solution for sum 5{5 }
{}

 Printing solution for sum 6{}
{}

 Printing solution for sum 11{}
{}

 Printing solution for sum 16{}
{}

 Printing solution for sum 17{}
{}

Since {1,5,5} and {11} is a solution, in this case, the expected output should be Printing Solution for sum 11 {1,5,5} and {11} but it's not displaying that.

What is the problem and how can I fix it?

chqrlie · Accepted Answer

Your algorithm is too complicated. You start on the correct path, computing the sum of all subsets of the set, but you do not correctly compute all possible disjoint subsets to try and find one with the same sum.

Here is a simpler approach:

enumerate all subsets
for each subset, compute the sum and store a structure with the subset signature and its sum into an array.
sort the array by the value of the sum
iterate over the sorted array:
for each element, iterate over the subsequent elements with the same sum, if one of them has a disjoint subset signature, you have a match, print it.
the space complexity is O(2^N) and the time complexity is even worse at O(2^N+1), which is very bad, but manageable for small sets.

Here is a modified version:

#include 
#include 

struct s { int sig, sum; };

int compare(const void *p1, const void *p2) {
    int sum1 = ((const struct s*)p1)->sum;
    int sum2 = ((const struct s*)p2)->sum;
    return (sum1 > sum2) - (sum1 < sum2);
}

void print_set(int arr[], size_t sig) {
    printf("{");
    while (sig) {
        if (sig & 1)
            printf(" %d", *arr);
        arr++;
        sig >>= 1;
    }
    printf(" } ");
}

void partition(int arr[], int n) {
    size_t i, j, count = 1ULL << n;
    struct s *array = calloc(sizeof(*array), count);
    int b, sum;

    if (array != NULL) {
        for (i = 1; i < count; i++) {
            sum = 0;
            for (b = 0; b < n; b++) {
                if (i & (1ULL << b))
                    sum += arr[b];
            }
            array[i].sig = i;
            array[i].sum = sum;
        }
        qsort(array, count, sizeof(*array), compare);
        for (i = 0; i < count; i++) {
            for (j = i + 1; j < count && array[i].sum == array[j].sum; j++) {
                if ((array[i].sig & array[j].sig) == 0) {
                    printf("solution with sum=%d: ", array[i].sum);
                    print_set(arr, array[i].sig);
                    print_set(arr, array[j].sig);
                    printf("
");
                }
            }
        }
        free(array);
    }
}

int main() {
    int *arr, n, i;
    printf("Enter the number of elements in the set: ");
    if (scanf("%d", &n) == 1) {
        arr = (int*)malloc(sizeof(int) * n);
        if (arr != NULL) {
            printf("Enter the set elements: ");
            for (i = 0; i < n; i++) {
                if (scanf("%d", &arr[i]) != 1)
                    return 1;
            }
            partition(arr, n);
            free(arr);
        }
    }
    return 0;
}

Output:

Enter the number of elements in the set: 3
Enter the set elements:  1 2 3
solution with sum=3: { 3 } { 1 2 } 

Enter the number of elements in the set: 4
Enter the set elements: 1 2 3 4
solution with sum=3: { 1 2 } { 3 }
solution with sum=4: { 4 } { 1 3 }
solution with sum=5: { 2 3 } { 1 4 }

Enter the number of elements in the set: 4
Enter the set elements: 1 5 11 5
solution with sum=5: { 5 } { 5 }
solution with sum=11: { 11 } { 1 5 5 }

Algorithms: To determine whether a given set has two subsets which are disjoint such that sum of elements in both subsets is same?

Answers (2)

Related Questions