CareerCup

1. sum the first k element from array.
2. Start a loop from k+1 element to end.
3. inside the loop, add current element to the current sum and subtract (current ptr - k)th value from the sum.
4. Whenever sum is equal to ssum, keep that as result.

The solution given in the first reply seems to be working in O(n). Why bother DP here?

Here is the code (this is a recursive solution, and quite obviously it is exponential). DP-fying it should be pretty easy given the recursive code:

The code is in C# and is 100% working. You can simply copy paste it in a Console Application and hit Run :)

public void SubsetSum()
        {
            int[] arr = { 7, 6, 5, 1, 11, 2, 9, 17, 3, 4, 0 };
            SubsetSum(arr, 3, 0, 9, 0, 0, "");
            Console.ReadLine();
        }
        private void SubsetSum(int[] arr, int k, int elementsPickedSoFar, int targetSum, int sumSoFar, int i, string subsetSum)
        {
            if (k >= arr.Length) return;

            if (i >= arr.Length)
            {
                if (elementsPickedSoFar == k && targetSum == sumSoFar)
                    Console.WriteLine(subsetSum);

                return;
            }

            if (elementsPickedSoFar == k)
            {
                if (targetSum == sumSoFar)
                    Console.WriteLine(subsetSum);

                return;
            }

            SubsetSum(arr, k, elementsPickedSoFar, targetSum, sumSoFar, i + 1, subsetSum);
            SubsetSum(arr, k, elementsPickedSoFar + 1, targetSum, sumSoFar + arr[i], i + 1, subsetSum + " " + arr[i].ToString());
        }

Let me explain the recurrence in English:

1. In each step of the recursion, you don't pick the current element from the array (denoted by i) and DO NOT add anything to the sum (denoted by sumSoFar)
2. OR, you pick the current element from the array (denoted by i) and it to the sum (denoted by sumSoFar)

3. That's it! All that is left are the bases cases, which are pretty self-explanatory, but to give a quick rundown:
3i. You terminate when i >= arr.Length (quite obviously)
3ii. OR the total elements that you have picked so far (refer to Step 1) is equal to 'k' (max elements you can pick).

#include<stdio.h>
int maxSubArraySum(int a[], int size)
{
int max_so_far = 0, end = 0;
int i;
for(i = 0; i < size; i++)
{
end = end + a[i];
if(end < 0)
end = 0;

else if (max_so_far < end)
max_so_far = end;
}
return max_so_far;
}

/*Driver program to test maxSubArraySum*/
int main()
{
int a[] = {-2, -3, 4, -1, -2, 4, 5, -3};
int max_sum = maxSubArraySum(a, 8);
printf("Maximum contiguous sum is %d\n", max_sum);
getchar();
return 0;
}

My solution in Scala. It could be event shorter with recursive function but this way it is simpler.

def calculate(a:Array[Int], subArrSize:Int, expSum:Int):Int = {
    var res = 0;
    for (startPoint <- 0 to a.size) {
      val subArray = a.drop(startPoint).take(subArrSize);
      if (subArray.size == subArrSize && subArray.reduceLeft(_+_) == expSum) {
        res += 1
      }
    }
    return res;
  }

  val arr = Array(1,2,3,5,-2,3,0)
  println("Res:" + calculate(arr, 2, 3))

int count = 0;
int sum = 0;
for(int i=0; i<k; i++)
  sum += a[i];	// sum will hold sum of first k elements
for(int i=k; i<n; i++)
{
  sum = sum + a[i] - a[i-k];  // sum has 0 - (k-1) elements sum, next time we need to check
  if(sum == targetsum)       // 1 - k elements sum, for this we will add kth element and 
    count++;		            // substract 0 element (i-k)
}

import java.util.ArrayList;
import java.util.List;


public class ArrayBiggestSumPath {

List sumlist = new ArrayList();

List findsubset(int[] a,int sum,int index)
{
List allsublist = new ArrayList();
if(index<0)
{
allsublist.add(new ArrayList());
return allsublist;
}
int element = a[index];
allsublist = findsubset(a,sum,index-1);
List mothersubset= new ArrayList();
for (int i = 0; i < allsublist.size(); i++) {
List l = (List)allsublist.get(i);
List newlist=new ArrayList();
newlist.addAll(l);
newlist.add(element);
if(findsum(newlist)==sum)
sumlist.add(newlist);
mothersubset.add(newlist);
}
allsublist.addAll(mothersubset);
return allsublist;
}
int findsum(List list)
{
int sum=0;
for (int i = 0; i < list.size(); i++) {
sum+=(Integer)list.get(i);
}
return sum;
}
public static void main(String[] args) {
int a[]={4,5,8,3,54,23,44};
int sum=28;
ArrayBiggestSumPath o = new ArrayBiggestSumPath();
o.findsubset(a, 31, a.length-1);
System.out.println(o.sumlist);
}
}

The Dp solution is for positive integers

import java.io.*;
import java.util.*;

public class AllSumSubset{
public void displaySubSet(int setN[]) {
int length = setN.length;
int i;
int sumofnumber =0;
int sumofaset = 0;
int sumofnumberinaset=0;
try {
//BufferedWriter writer = new BufferedWriter(new FileWriter(new File("Results")));
for (i = 0; i < (1 << length); i++) {
for (int j = length-1; j >-1; j--) // We don't need the last one
{

if ((i & (1 << j)) != 0)
{
// writer.write("" + setN[j] + " ");
sumofaset+=setN[j];
sumofnumberinaset+=1;
}
if(sumofaset>setN[length-1])
break;
}

Arrays.sort(setN);
if((Arrays.binarySearch(setN,sumofaset)>0)&&sumofnumberinaset!=1)
{
sumofnumber=sumofnumber+1;
//writer.write("ok");
}

sumofaset=0;
sumofnumberinaset=0;
// writer.write("\r\n");
}
// writer.close();
System.out.println(sumofnumber);
} catch (Exception e) {
}
}

public static void main(String[] args) {
AllSumSubset ss = new AllSumSubset();
int setN[] = { 3, 4, 9, 14, 15, 19, 28, 37, 47, 50, 54, 56, 59, 61, 70, 73, 78, 81, 92, 95, 97, 99};
Arrays.sort(setN);


System.out.println(Arrays.binarySearch(setN,7)<0);
ss.displaySubSet(setN);
}
}

This is actually a variant of the subset problem. Just make a few modifications on the original algorithm as follows:

public static LinkedList<Integer> subset = new LinkedList<Integer>();
  public static void getSubset(int[] a, int i, int k, int ssum) {
    if (i == a.length) {
      if (subset.size() == k) {
        int sum = 0;
        for (int e : subset) {
          sum += e;
        }
        if (sum == ssum) {
          for (int e : subset) {
            System.out.print(e + " ");
          }
          System.out.println();
        }
      }
      return;
    }
    subset.add(a[i]);
    getSubset(a, i + 1, k, ssum);
    subset.removeLast();
    getSubset(a, i + 1, k, ssum);
  }

Partition problem. Dynamic Programming solution mentioned in Wikipedia and keeping the number of elements in a sum additionally.

Partition problem. Dynamic Programming solution mentioned in Wikipedia and keeping the number of elements in a sum additionally.

onestopinterviewprep.blogspot.com/2014/03/namespace-arrayproblem-write-function.html