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