CODEWITHSUNDEEP
calgorithmrecursiondata-structuresseries
Zamkie
Zamkie

Reputation: 89

recursion - data structure course - print all possible series

I need to print all possible series that their sum is equal to N; for example is n == 4 the output should be:

[1, 1, 1, 1]
[1, 1, 2]
[1, 2, 1]
[1, 3]
[2, 1, 1]
[2, 2]
[3, 1]
[4]

My way of thinking to solve this problem was: print the series that the number i is not in the series print the series that the number i is in the series, now need to find the sum of N-i.

my code:

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

void printArr(int arr[], int n)
{
    for (int i = 0; i < n; i++)
    {

        printf(" %d ", arr[i]);
    }
    printf("\n");

}

void printAllHelper(int* a,int size, int sum, int used,int index) {
    if (sum == 0) {
        a -= used;
        printArr(a, used);
    }
    else if (sum < 0 || index == size) 
    {
        return;
    }
    else {
        for(int i = 1 ; i <= size ; i ++) 
        {
            printAllHelper(a, size, sum, used, index + 1);
            if (i <= sum)
            {
                *a = i;
            }
            printAllHelper(a+1, size, sum -i, used +1, index + 1);


        }




    }

}

void printAll(int num) {
    int* myArray = (int*)malloc(num * sizeof(int));
    printAllHelper(myArray,num,num,0,0);

}

void main() {
    printAll(4);
}

my output:

 3  1
 3  1
 3  1
 3  1
 3  1
 3  1
 3  1
 3  1
 3  1
 4
 1  3
 4
 2  2
 4
 3  1
 4
 4
 1  3
 1  1  2
 1  3
 1  2  1
 1  3
 1  3
 1  3
 4
 1  3
 4
 2  2
 4
 3  1
 4
 4
 2  2
 2  1  1
 2  2
 2  2
 2  2
 2  2
 4
 1  3
 4
 2  2
 4
 3  1
 4
 4
 3  1
 3  1
 3  1
 3  1
 3  1
 4
 1  3
 4
 2  2
 4
 3  1
 4
 4
 4
 4

Please try to explain to me your way of thinking, and how you approach this kind of problem, I want to be the very best like no one ever was :(.....

Upvotes: 4

Views: 82

Answers (1)

tobias_k
tobias_k

Reputation: 82899

Your reasoning is not quite correct, but your code is almost right. The loop in your else part should be

    for(int i = 1 ; i <= sum ; i ++)  {
        *a = i;
        printAllHelper(a+1, size, sum-i, used+1, index+1);
    }

With this, I get the output

 1  1  1  1 
 1  1  2 
 1  2  1 
 1  3 
 2  1  1 
 2  2 
 3  1 
 4

The idea is basically: "The numbers sum to sum if the first number i is any number from 1 to sum and the rest of the numbers sum to sum - i."

Also, note that your code shows some room for improvement, e.g. the used and index variables seem a bit redundant. And with not adding numbers larger than sum or smaller than 1, the check whether sum < 0 || index == size is not necessary, either. Thus you also do not need the size parameter. Your printAllHelper could be simplified to something like this:

void printAllHelper(int* a, int sum, int index) {
    if (sum == 0) {
        printArr(a, index);
    } else {
        for(int i = 1 ; i <= sum ; i++)  {
            a[index] = i;
            printAllHelper(a, sum-i, index+1);
        }
    }
}

(Note: C is not my native language, if you see more things to improve, please comment.)

Upvotes: 5

Related Questions