Thursday, May 1, 2014

Check whether subsequence sum is equal to given number


public class SubSeqSum {
    static int arr[] = {1, 4, 10, 20, 34};
   static int elemSum = 25;
   Object o;
   public static void main(String[] args) {
      // SubSeqSum.testDynamicApproach();
       boolean found = SubSeqSum.testUsingRecursiveApproach(0, elemSum);
      if (found){
                 System.out.println("Sum FOund");
       }else{
                System.out.println("sum not found");
       }
 }
 private static boolean testUsingRecursiveApproach(int index,int elemSum) {
    if (elemSum == 0){
        return true;
    }
    if ( ((index+1) > arr.length) || (elemSum <0) )
           return false;
 
 
  if ( testUsingRecursiveApproach((index+1), elemSum - arr[index]) || testUsingRecursiveApproach((index+1), elemSum) )
         return true;
  else
         return false;
 
 }
 private static void testDynamicApproach() {
   int temp[] = new int[arr.length];
 
   for (int i=0;i<arr.length;i++){
       for (int j=0;j<(i+1);j++){
            temp[j] = temp[j] + arr[i];
            if (temp[j] == elemSum){
                 System.out.println("Sum foound");
            }
        }
    }

 
 }
}

 

No comments:

Post a Comment