## Search This Blog

Simplicity is the ultimate sophistication.” — Leonardo da Vinci
Contact me: sreramk360@gmail.com

## Friday 27 March 2015

### An example program for control statements and conditional statements

An example program for control statements and conditional statements

/*
* An example program for control statements and conditional statements
* problem: write a program to solve the following problem:
*    statement: Let there be an integer array A with n elements. Lets say that
*    we choose m numbers from the n numbers (a number can be chosen twice) and add them
*    to obtain the value x. So algorithmically determine the number of combinations
*    possible to bring about the sum x. Note: the values can be repeated.
**** By K Sreram
*/

#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
int evaluateSum(int* array, int size)
{
int i, s = 0;
for (i = 0; i<size; ++i)
s += array[i];
return s;
}

void display(int *array, int size)
{
int i;
for (i = 0; i < size; ++i)
printf("\n%d", array[i]);
printf("\n\n");
}
int evaluate(int *instant, int depth,
const int *mainArray, const int size_mainArray,
const int maxDepth, const int result)
{
int i;
static unsigned long long int count = 0;

if (depth == 0)   count = 0; // this ensures that this function can be used for a second time

if (depth == (maxDepth - 1)) // base case
for (i = 0; i<size_mainArray; ++i)
{
instant[depth] = mainArray[i];
if (evaluateSum(instant, depth+1) == result) // condition is checked and the combination is displayed
{
display(instant, depth+1);
++count;
}
}
else if (depth < (maxDepth - 1))
{
++depth;
for (i = 0; i<size_mainArray; ++i)
{
instant[depth - 1] = mainArray[i]; // this creates the array that's being checked
// the condition is checked in the base case
evaluate(instant, depth, mainArray, size_mainArray, maxDepth, result);
}
}
return count;
}
void getElements(int* array , int size)
{
int i, r;
for(i = 0; i<size; ++i)
{
scanf("%d", &r);
array[i] = r;
}
}

/// this program runs at O(2^(N+1)) time complexity and O(N) space complexity. The solution is inefficient for larger values
int main()
{
int result;
int *mainArray;
int size_mainArray;
int *instantArray;
int size_instant;
printf("enter the size of the main array:");
scanf("%d", &size_mainArray);
printf("\nenter the size of the summation:");
scanf("%d", &size_instant);
mainArray = malloc(sizeof(int)*size_mainArray);
instantArray = malloc(sizeof(int)*size_instant);
printf("\nenter the elements: ");
getElements(mainArray, size_mainArray);
printf("enter result:");
scanf("%d", &result);
int count = evaluate(instantArray, 0, mainArray, size_mainArray, size_instant,result);
printf("\n number of combinations possible: %d", count);
getch();
return 0;
}