Hello!!! So I am back after yet another loooooooong break from this blog. And this time I have a small but interesting problem whose solution I have just worked out...The problem is what I call "The random addition problem". Actually, this problem is a very simple one, one which most of us must have encountered in our day to day life...like giving changes for a given sum of money and many more. OK, so lifting the veil off, the problem is to find a subset of a set of numbers whose sum is equal to a given random number or to show failure if no such subset exists. So, the problem is precise, concise and clear :). Lets have an instance:
Test random number : 132,
Set of numbers: 24 3 17 8 96 43 6 55 89 998 254 678 123 90 546 46 32 5;
Now here the random number 132 can be made by adding the numbers of the subset (3,6,123) of this set.
Now think about this, "How did we come up with this set?". Naturally our brain goes on with doing this so fast that we don't recognize its process until we come up with a really long list or a really large number. But a little thinking can make it clear that we first try to grab the largest number (lets say 'K') of the set which is smaller than the given random number (lets say 'N'). Then we look for other number(s) in the set which can complement this number K to get the final number N. So essentially this is a recursive problem.
However, the other approach that looks straight-forward and brute-force but is quite often tricky, lengthy and may not come up with an answer is to simply keep on adding numbers starting from the beginning an d to go on until you find the number "N" or you end the list or you get a number > 'N'. Now this approach is not complete and as I said earlier may not come up with an answer even though the answer may exist. This is primarily due to the fact that this approach of adding numbers to a running sum can't accommodate for the fact that the required subset may comprise of numbers at different positions in the set.
So, now after all this discussion it quite clear that we should go with the recursive algo...(at least I'm going with it :) ).
So the first thing that we do is to eliminate all those numbers in the set (or array 'A[]' as we may call it) which are greater than 'N' because they are actually useless for us (You don't need an explanation for this... do you??? :P). Then we must sort the numbers in an ascending order. In my code I have done all this at the time of user input itself by using insertion sort. Next, we need to pop the numbers from this array (i.e. send the largest numbers one by one) into the recursive function. Once a number goes into the recursive function, we subtract it from 'N' and get a new number, say 'P'. This 'P' is the new number 'N' which we are now looking for in the list. If found our problem is solved, else we go on breaking this number 'P' by selecting the next highest number smaller than 'P' from the original array A[]. We can limit the search for the requisite number by a limiting pointer to this number. The recursion exits if this pointer reaches the first number in the array or the number to search 'P' becomes less than the least number in the array. The iteration then continues with the next highest number until we get a complete sequence or the whole array is finished.
Below is my simple C code for the problem. I think there are quite a few optimizations left in the code. This returns a sequence if it finds one or returns No if no answer is found...
Please post your comments if you find some optimizations or have some advice.
#include
#include
void print_array(int arr[], int len);
void copy_array(int arr1[], int arr2[], int len);
int check_for_sum(int num); //the main recursive function that does the job.
int found_in_b(int number);
int smaller_than_in_b(int numb);
int add_array(int arr[], int pntr);
//Global declarations
int num;
int num_needed;
int a[20];
int b[20];
int stack[20];
int stck_pntr = 0;
int a_len = 0;
int b_ptr = 0;
int add_array(int arr[], int pntr){
int sum = 0;
int i = 0;
while(i < pntr){
sum += arr[i];
i++;
}
return sum;
}
void print_array(int arr[], int len){
int i = 0;
while(i < len){
printf("%d, ",arr[i]);
i++;
}
}
void copy_array(int arr1[], int arr2[], int len){
int i = 0;
while(i < len){
arr2[i] = arr1[i];
i++;
}
}
int found_in_b(int number){
int i = 0;
while(i < b_ptr){
if(b[i] == number)
return 1;
i++;
}
return 0;
}
int smaller_than_in_b(int numb){
int index = 0;
while((index < b_ptr) && (b[index] < numb)){
index++;
}
b_ptr = --index;
return b[index];
}
int check_for_sum(int number){
num_needed -= number;
if(num_needed < a[0] || (b_ptr<=1 && num_needed!=b[0]))
return 2;
else if(found_in_b(num_needed)==1 || num_needed==0)
return 1;
else{
number = smaller_than_in_b(num_needed);
stack[stck_pntr++] = number;
return check_for_sum(number);
}
}
int main(int argc, char *argv[]){
printf("Enter the number to test: ");
scanf("%d",&num);
num_needed = num;
printf("Enter the numerical array (Enter -1 to exit):\n");
int last = 0;
do{
int gen;
scanf("%d",&gen);
if(gen > 0){
if(gen <= num){
while(gen < a[last-1] && last != 0){
a[last] = a[last-1];
last--;
}
a[last] = gen;
a_len++;
last = a_len;
}
}
else{
break;
}
}while(a_len < 20);
int i = a_len - 1;
int val = 0;
while(i>=0){
copy_array(a, b, i);
b_ptr = i;
num_needed = num;
stck_pntr = 0;
stack[stck_pntr] = a[i];
stck_pntr++;
val = check_for_sum(a[i]);
i--;
if(val==1)
break;
else
continue;
}
if(val(equal to)1){
printf("\nYes. You can use the series:\n");
print_array(stack, stck_pntr);
stck_pntr = add_array(stack, stck_pntr);
printf("%d.\n",num - stck_pntr);
}
else
printf("\nNo\n");
system("PAUSE");
return 0;
}
