CareerCup

I think;
Recursive -> O(2^n)
Non-Recursive (Dynamic programming) -> O(n^2)

It looks line

O(n^4)

to me for non recursive solution.

Dynamic programming just gives a yes and no answer....how do you get it in O(n2) by DP?

How about this: non-recursive O(n^2)

int FindSumCount(int arr[], int n)
{
	int sum=0;
	int count=0;

	for(int i=0;i<n;i++)
	{
		sum=0;
		for(int j=i;j<n;j++)
		{
			sum += arr[j];

			if(sum == 15)
				count++;
			else if(sum<15)
				continue;
			sum -= arr[j];
		}
	}
	return count;
}

// Here is recursive one


static int total=0;
void FindSumCombo(int *, int, int, int);
const int ALLSUM=15;
int _tmain(int argc, _TCHAR* argv[])
{
	
	int* arr = new int[argc-1];
	for(int i=1;i<argc;i++)
	{
		arr[i-1]=_ttoi(argv[i]);
	}

	for(int i=0;i<5;i++)
		FindSumCombo(arr,0,i,4);
	std::cout<<total;
	return 0;
}

void FindSumCombo(int* arr, int sum, int start, int end)
{
	if(start==end)
	{
		if(arr[start]+sum==ALLSUM)
		{
			total++;
			return;
		}
		else
		{
			return;
		}
	}
	if(arr[start]+sum==ALLSUM)
	{
		total++;
		FindSumCombo(arr,sum,1+start,end);
	}
	if(arr[start]+sum>ALLSUM)
	{
		FindSumCombo(arr,sum,1+start,end);
	}
	if(arr[start]+sum<ALLSUM)
	{
		FindSumCombo(arr,sum+arr[start],start+1,end);
	}
	return;

	
}