CareerCup

//Use Recursion to solve it...runtime depends on array size and group size
//Brute force solution, generates nCg combinations
//where n - no. of elements & g - groupsize
//

#include<iostream>

int sum_number(int sum,int *arr,int index,int size,int gsize,int total);

int group[20],count=0;

void main()
{
	int arr[] = {3,4,16,2,13,8,5,7,2,9};

	sum_number(0,arr,0,sizeof(arr)/4,4,28);
}

int sum_number(int sum,int *arr,int index,int size,int gsize,int total)
{
	if(gsize>0)
	{
		for(int i=index;i<size;i++)
		{
			sum = sum + arr[i];
			group[count++] = arr[i];
			sum_number(sum,arr,i+1,size,gsize-1,total);
			count--;
			sum = sum - arr[i];
		}
	}
	else
	{
		if(sum==total)
		{
			for(int i=0;i<count;i++)
			{
				printf("%d ",group[i]);
			}
			printf("Sum %d\n",sum);
		}
	}
	return sum;
}

I came up with a N^2 algorithm. Can we improve it ? Any comments ?

This is an instance of knapsack problem. So we can use dynamic programming. The 'total' given can be thought of as the total value. The individual numbers represent individual values. Thee group size can be thought of as the weight constraint. Each number adds a weight equals 1. Solve the knapsack now.

This is a sum of sums problem - NP complete.

Using the knapsack algorithm will work (knapsacks are limited to size 3)

knapsack alrite...but knapsack does not account for multiple solutions...need some tweak so we do not return as soon as we fill the sack once... need to keep continuing after printing the result to check for other possiblites...

I agree with King_k. Brutal force solution would be O(N^2 * log(n)).

First, sort the array, takes O(nlogn). Then, iterate through first and second dimension with N^2, the last one would be found with binary search. Overall time complexity is O(N^2 * log(n)).

find the subset of the array of the size "groupsize" and test whether the total equals to the given total.

how can we use DP here?its not an optimization problem in terms of the sums...?