Persistent Systems Interview Question
Software Engineer / DevelopersCountry: India
Interview Type: Written Test
public class SubSetSumProblem {
public static void main(String s[]){
int set[] = {3, 34, 4, 12, 5, 2};
int sum = 9;
System.out.println(isSum(set, 0, 5, sum));
}
public static boolean isSum(int arr[] , int fromIdx, int toIdx, int sum){
if(fromIdx == toIdx){
if(arr[fromIdx] == sum)
return true;
else
return false;
}
boolean prob1Rslt = isSum(arr , 0 , toIdx -1 , sum - arr[toIdx]);
boolean prob2Rslt = isSum(arr , 0 , toIdx -1 , sum );
return prob1Rslt || prob2Rslt;
}
}
class Solution {
public static int solution(int[] A, int S) {
int output=0;
int length=0;
int temp=0;
int temp1=0;
for(int i=0;i<A.length;i++){
for(int j=i+1;j<A.length;j++){
output=new Integer(A[i]) + new Integer(A[j]);
if(output==S){
length++;
temp=j-i;
if(temp>temp1){
temp1=temp;
}
}
}
}
if(length!=0){
return temp1+1;
}else{
return -1;
}
}
public static void main (String args[]){
int[]arr1={0,1,-1,1,4,-1,0};
System.out.println(" Highest Length is ="+solution(arr1,5));
}
}
If i am not wrong, this question is actually sum of subsets
- ayusun September 14, 2014