CareerCup

its a dynamic programming problem

void FindSumElem(int a[] , int size , int num){

	vector<int> v;
	for(int i = 0 ; i < size ; i++){
	
	int index = i;
	int sum = 0;
	int j = i;
		
	for(; j < size ; j++){
		
	sum =sum + a[j];
	v.push_back(a[j]);

	if(sum == num){
	
	cout << "Num found "<<num<< " " << sum << endl;
	for(vector<int>::iterator it = v.begin() ; it != v.end() ; it++)
	cout <<*it<<endl; 
	return;
	}

	if(sum > num ){
	//make j point to next element
	//EX. if a [] = {-1 , 0 ,3 } if previous j was at index 0 i.e. a[j] == -1 
	//now make it point to index 1 i.e a[j] == 0
	//Basically i am skipping the element pointed by J as it is not part of solution
	j = ++index;
	//Flush the vector and start again 
	v.clear();
	v.push_back(a[i]);
	sum = a[i];
	}
  }
}
	cout << "No such elements"<<endl;
}

int main( )
{	

	int a[] = {-1,0,3,4,5,6};
	FindSumElem(a,6,9
		);	
	return 0;
}

Guys your comments are welcome also try it with diff i/p and let me know of any bugs

P.S. please use Reply to Comment so i will come to know if anybody has replied

Recursive version - (Not iterative, recursion means same function is called by itself on itself for itself)

bool sum(int *a, int start, int end, int val){
	if(start>end)return false;
	for(int i=start;i<=end;++i){
		if(a[i]<val){
			if(sum(a,i+1,end,val-a[i])){
				return true;
			}
		}
		else if(a[i]==val){
			return true;
		}
	}
	return false;
}

Is this an NP-Complete problem called something like subset-sum?

ya david you are right...its a pretty basic NP-complete problem.
It can be solved by DP

ya david you are right...its a pretty basic NP-complete problem.
It can be solved by DP

void SubSetSum(int arr[], int start, int end, int PartialSum, int targetSum, vector<int> v){
   if (start >=end){
       if (partialSum == targetSum){
          for (int i=0; i < v.size();i++){
               cout << " " << v[i];
          }
          cout << endl;   
          return;        
       }
   }
   SubSetSum(arr, start+1, end, PartialSum + arr[start], targetSum, set.push_back(arr[i]);
   set.pop_back(arr[i]);
   SubSetSum(arr, start+1, end, PartialSum, targetSum, set);
}

Search for a pair which sums to S
Let A be a sorted array of integers ans S a target integer
Problem: Design an efficient algorithm for determining if there exist a pair of indices i,j (not necessarily distinct) such that A[i] + A[j] = S

SOL:
store the values from the array in a hashtable, then for each new value, check to see if its complement has already been seen and if so, what is the index.

What is the final time complexity of this algorithm (worst case)?

This solution will work only for positive numbers and time complexity is: n*sum

public void knapsack()
{
int[] a = { 0, 1, 2, 3, 4, 5, 6 };

// the value we are looking for
int sum = 10;
Boolean[,] k = new Boolean[a.Length, sum + 1];

k[0, 0] = true;

for (int s = 1; s <= sum; s++)
{
k[0, s] = false;
}


for (int iIndex = 1; iIndex < a.Length; iIndex++)
{
for (int s = 0; s <= sum; s++)
{

if (a[iIndex] <= s)
{
k[iIndex, s] = k[iIndex - 1, s] || k[iIndex - 1, s - a[iIndex]];
}
else
{
k[iIndex, s] = k[iIndex - 1, s];
}

}
}
// to display solution
DisplayKnapsack(a, k, sum);


}

private void DisplayKnapsack(int[] input, bool[,] output, int knapSackSize)
{
int m= input.Length - 1;
int n = knapSackSize;
if (!output[input.Length -1 , knapSackSize])
{
Console.WriteLine("Knapsack cant be completely filled with given collection of weights. Next best solution is ");
while(!output[m,n])
{
n--;
}
Console.WriteLine(n.ToString() + " and weights selected are : ");
}
else
{
Console.WriteLine("Knapsack can be completely filled with given collection of weights and the weights participated in the soultion are : ");
}

while(n> 0)
{
// this is to check if the smaller subset can also lead to the size of knapsack and giving priority to that
if(output[m - 1,n] == true)
{
m--;
}
else
{
Console.WriteLine(input[m]);
n -= input[m];
m--;
}
}

}