Check whether a given tree is symmetric with structure wise or not

How will you check whether a given tree is symmetric with structure wise or not.

Ex:
Symmetric (structure wise)
            5
          /   \
         3    9
         \   /
         4  8

 Not symmetric

            5
          /   \
         5     9
        /      /
       3     8

Implementation

class CheckForSymmetricTree{
static class Tree{
int data;
Tree left = null;
Tree right = null;

public Tree(int data){
this.data = data;
}

//create minimal bst
public static Tree createBST(int []a, int left, int right){
if(right < left)
return null;

int mid = (left + right)/2;
Tree root = new Tree(a[mid]);
root.left = createBST(a, left, mid - 1);
root.right = createBST(a, mid + 1, right);

return root;
}
}

public static boolean isSymmetric(Tree root){
if(root == null)
return true;

return isSymmetric(root.left, root.right);
}

public static boolean isSymmetric(Tree r1, Tree r2){
if(r1==null && r2==null)
return true;

if(r1==null || r2==null)
return false;

return (isSymmetric(r1.left, r2.right) && isSymmetric(r1.right, r2.left));
}

public static void main(String []args){
int []a = {1,2,3,4,5,6,7};

Tree root = Tree.createBST(a, 0, a.length - 1);

boolean result = isSymmetric(root);

if(result)
System.out.println("Given tree is a symmetric tree");
else
System.out.println("Given tree isn't a symmetric tree");
}

}

Output : Given tree is a symmetric tree

Given a array of 0's,1's and 2's arrange in a way that all 0's come first, then 1's then 2's.

Given a array of 0's,1's and 2's arrange in a way that all 0's come first, then 1's then 2's.

Method 1: (By using sorting)

        void arrange(int []array){
                if(array == null || array.length == 0)
                     return;
java.util.Arrays.sort(a);
}

Time Complexity : O(NlogN)

Method 2: (by counting the 0s, 1s and 2s)

       void arrange(int []array){
                if(array == null || array.length == 0)
                      return;

int countZeros = 0;
int countOnes = 0;
int countTwos = 0;

for(int i = 0; i < a.length; i++){
if(a[i] == 0)
countZeros++;   //count number of  zero
else if(a[i] == 1)
countOnes++;    //count number of  one
else if(a[i] == 2)
countTwos++;    // count number of two
}

for(int i = 0; i < countZeros; i++)
a[i] = 0;          //write zero to array

for(int i = countZeros; i <a.length-countTwos; i++)
a[i] = 1;          //write one

for(int i = countZeros+countOnes; i < a.length; i++)
a[i] = 2;          //write two
}

Time Complexity : O(N)

Method 3 : (By using Dutch flag algorithm)
     For Dutch Flag Algorithm, click here

      void arrange(int []a){
                if(array == null || array.length == 0)
                      return;

int min = Integer.MAX_VALUE;
int max = Integer.MIN_VALUE;

//Traverse the array once to pickup min and max values
for(int i = 0; i < a.length; i++){
if(a[i] > max)
max = a[i];
if(a[i] < min)
min = a[i];
}

int p = 0, q = a.length - 1;
int temp;  //for swapping values

for(int i = 0; i < q; i++){
if(a[i] == min){   //place the min value at the lowest position
temp = a[p];
a[p] = a[i];
a[i] = temp;
p++;
}
if(a[i] == max){   //place the max value at the highest position
temp = a[q];
a[q] = a[i];
a[i] = temp;
q--;
i--;
}
}
}

Time Complexity : O(N)

Segregate Even And Odd Numbers in given array

Given an array A[], write a function that segregates even and odd numbers. The functions should put all even numbers first, and then odd numbers.

Example
  Input = {12, 34, 45, 9, 8, 90, 3}
  Output = {12, 34, 8, 90, 45, 9, 3}

  In the output, order of numbers can be changed, i.e., in the above example 34 can come before 12 and 3 can come before 9.

Algorithm 
segregateEvenOdd(int []array)
     1) Initialize two index variables left and right:
            left = 0,  right = size -1
     2) Increment left index until we see an odd number.
     3) Decrement right index until we see an even number.
     4) If left < right then swap arr[left] and arr[right].

Implementation

class SegregateEvenAndOddNumbers{
 
    static void segregate(int []a){
        if(a == null || a.length == 0)
            return;
        
        int left = 0, right = a.length - 1;
        while(left < right){
            
            while(a[left]%2 == 0 && left < right)
                left++;
            
            while(a[right]%2 != 0 && left < right)
                right--;
            
            if(left < right){
                swap(a, left, right);
                left++;
                right--;
            }
        }
    }
   
     //Utility function to swap array elements
    static void swap(int []a, int i, int j){
        int t = a[i];
        a[i] = a[j];
        a[j] = t;
    }
 
    public static void main(String []ar){
        int []a = {12, 34, 45, 9, 8, 90, 3};
        segregate(a);
        System.out.println("\nafter the shuffling" + java.util.Arrays.toString(a));
    }
}

Find Minimum Number Of Swap Required To Sort Input Array

Given an array containing sequence of bits (0 or 1), you have to sort this array in the ascending order i.e. all 0' in first part of array followed by all 1's. The constraints is that you can swap only the adjacent elements in the array. Find the minimum number of swaps required to sort the given input array.

Example: Given the array (0,0,1,0,1,0,1,1) the minimum number of swaps is 3.

Implementation

int swapRequired(int []array){
       //Boundary condition
       if(array == null || array.length == 0)
             return 0;

       int swap = 0, count = 0;
        //iterate over all the elements of given array
       for(int i = array.length; i >= 0; i--){
               if(array[i] == 0)
                    count++;            //count the number of 0s between two 1s
               else
                    swap += count;
       }
       return swap;   //return the count of required swap
}

Selection Sort

Selection sort is a sorting algorithm, specifically an in-place comparison sort.

The algorithm works as follows:
1) Find the minimum value in the list.
2) Swap it with the value in the first position.
3) Repeat the steps above for the remainder of the list (starting at the second position and advancing each time).

Ex: Given array : 64 25 12 22 11
  After first step : 11 25 12 22 64
   After Second Step : 11 12 25 22 64
  After third step : 11 12 22 25 64
  After fourth step : 11 12 22 25 64

Implementation

class SelectionSort{
//method for selection sort
public static void selectionSort(int []a,int size){
int min;

for(int i = 0; i < size-1; i++){
min = i;
for(int j = i+1; j < size; j++){
if(a[min] > a[j]){
min = j;   //find the index of minimum value
}
}
if(min != i)
swap(a, i, min);
}
}

//Utility function to swap the elements in array
public static void swap(int []a, int i, int j){
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}

public static void main(String []args){
int a[] = {5,1, 4, 2, 8};

selectionSort(a, a.length);
System.out.println("elements of array after sorting..."+java.util.Arrays.toString(a));
}
}

Insertion Sort

Every repetition of insertion sort removes an element from the input data, inserting it into the correct position in the already-sorted list, until no input elements remain.

Example: The following table shows the steps for sorting the sequence {3, 7, 4, 9, 5, 2, 6, 1}.
3 7 4 9 5 2 6 1
3 7 4 9 5 2 6 1
3 7 4 9 5 2 6 1
3 4 7 9 5 2 6 1
3 4 7 9 5 2 6 1
3 4 5 7 9 2 6 1
2 3 4 5 7 9 6 1
2 3 4 5 6 7 9 1
1 2 3 4 5 6 7 9

Key points:
   1) Simple implementation
   2) Efficient for (quite) small data sets
   3) Adaptive (i.e., efficient) for data sets that are already substantially sorted: the time complexity is O(n +          d), where d is the number of inversions
   4)More efficient in practice than most other simple quadratic (i.e., O(n2)) algorithms such as selection sort        or bubble sort; the best case (nearly sorted input) is O(n)
   5)Stable; i.e., does not change the relative order of elements with equal keys
   6)In-place; i.e., only requires a constant amount O(1) of additional memory space
   7)Online; i.e., can sort a list as it receives it

class InsertionSort{
//method for insertion sort
public static void insertionSort(int []a, int size){
int temp;

for(int i = 1; i<size; i++){
for(int j = i; j > 0; j--){
if(a[j-1] > a[j]){
temp = a[j-1];
a[j-1] = a[j];
a[j] = temp;
}
}
}
}

public static void main(String []args){
int a[] = {5,1, 4, 2, 8};
insertionSort(a, a.length);
System.out.println("elements of array after sorting..."+java.util.Arrays.toString(a));
}
}

Time Complexity  : O(N^2) worst and average case
Space Complexity : O(1)

Bubble Sort

Algorithm :
Starting from the beginning of the list, compare every adjacent pair, swap their position if they are not in the right order (the latter one is smaller than the former one). After each iteration, one less element (the last one) is needed to be compared until there are no more elements left to be compared.

After first pass, largest element will be at the end of the array.

Ex:
Let us take the array of numbers "5 1 4 2 8", and sort the array from lowest number to greatest number using bubble sort algorithm. In each step, elements written in bold are being compared. Three passes will be required.
First Pass:
( 5 1 4 2 8 )  ( 1 5 4 2 8 ), Here, algorithm compares the first two elements, and swaps them.
( 1 5 4 2 8 )  ( 1 4 5 2 8 ), Swap since 5 > 4
( 1 4 5 2 8 )  ( 1 4 2 5 8 ), Swap since 5 > 2
( 1 4 2 5 8 )  ( 1 4 2 5 8 ), Now, since these elements are already in order (8 > 5), algorithm does not swap them.

Second Pass:
( 1 4 2 5 8 )  ( 1 4 2 5 8 )
( 1 4 2 5 8 )  ( 1 2 4 5 8 ), Swap since 4 > 2
( 1 2 4 5 8 )  ( 1 2 4 5 8 )
( 1 2 4 5 8 )  ( 1 2 4 5 8 )
Now, the array is already sorted, but our algorithm does not know if it is completed. The algorithm needs one whole pass without any swap to know it is sorted.

Third Pass:
( 1 2 4 5 8 )  ( 1 2 4 5 8 )
( 1 2 4 5 8 )  ( 1 2 4 5 8 )
( 1 2 4 5 8 )  ( 1 2 4 5 8 )
( 1 2 4 5 8 )  ( 1 2 4 5 8 )

Implementation:

class BubbleSort{
//method for the bubble sort
public static void bubbleSort(int a[], int size){
int temp = 0;
for(int i = 0; i < size-1; i++){
for(int j = 0; j < size-i-1; j++){
if(a[j] > a[j+1]){
temp = a[j];
a[j] = a[j+1];
a[j+1] = temp;
}
}
}
}

public static void main(String []args){
int a[] = {5,1, 4, 2, 8};

bubbleSort(a, a.length);
System.out.println("elements of array after sorting..."+java.util.Arrays.toString(a));
}
}

Find the Best Time To Buy And Sell Stock

Say you have an array for which the ith element is the price of a given stock on day i.
If you were only permitted to buy one share of the stock and sell one share of the
stock, design an algorithm to find the best times to buy and sell.

Ex:
Input = {6,1,3,2,4,7}
Output : time to buy = at index 1(value = 1)
             time to sell  = at index 5(value = 7)
             max profit   = 7 - 1 = 6

class BestTimeToBuyAndSellStock{
static void find(int []a){
//Boundary Condition
if(a == null || a.length == 0)
return;

int buy = -1, sell = -1, max = Integer.MIN_VALUE;
int min = 0, diff;
 
  for(int i = 1; i < a.length; i++){
if(a[i] < a[min])
min = i;

diff = a[i] - a[min];
if(diff > max){
max = diff;
buy = min;
sell = i;
}
}
System.out.println("buy "+buy+"\nSell "+sell+"\nMax "+max);
}

public static void main(String... args){
int []array = {6,1,3,2,4,7};
find(array);
}
  }

Time Complexity : O(N)
Space Complexity : (1) 

Serialization in java

In java, Serialization is a process used to convert object into the binary format which can be persisted into disk or sent over the network.
So when is Serialization used? Serialization is used when we want to persist the object. It is also used by RMI(Remote Method Invocation) to  pass objects between JVMs.

Java provides Serialization API for serializing and deserializing an object which includes java.io.Serializable, java.io.Externalizable, ObjectInputStream, ObjectOutputStream.

How Serialization is performed in java?
      To persist an object in java, first step is to flatten an object. For that, the respective class should implement the java.io.Serializable interface. We don't need to override any method because the Serializable interface is a marker interface.(Marker interface is a interface that does not have any methods)

class SerializableClass implements java.io.Serializable{
}

Now we marked the object for flattening.

Next Step is to persist the object. To persist the object, we use the java.io.ObjectOutputStream.

class SerializableClass implements java.io.Serializable{
     //Utility to write object into file
     static void saveObject(SerializableClass object){
            FileOutputStream fos = null;
            ObjectOutputStream oos = null;
            
            try{
                    fos = new FileOutputStream("test.ser");
                    oos = new ObjectOutputStream(fos);
                    oos.writeObject(object);  
                    oos.close();
            }catch(IOException e){}
     }
   
      //Utility to read the object from file
      static  SerializableClass readObject(){
               FileInputStream fis = null;
               ObjectInputStream ois= null;
               SerializableClass object = null;
               try{
                       fis = new FileInputStream("test.ser");
                       ois = new ObjectInputStream(fis);
                       object = (SerializableClass)ois.readObject();
                       ois.close();
               }catch(IOException e){}
              return object;
      }   

     public static void main(String... args){
             SerializableClass  object = new SerializableClass ();
             saveObject(object);
     }
}

References:
1. http://docs.oracle.com/javase/6/docs/api/java/io/Serializable.html
2. http://docs.oracle.com/javase/7/docs/platform/serialization/spec/serial-arch.html

Decode the given string

Given a input encoded string find the no. of ways it can be decoded.(we encode A-1 , B-2 , C-3...)

Example:
Input : "311316" (encoded string)
output : 6 

How? 
 word CAMP encoded as 311316. It can be decoded as 3 11 3 16 (CKCP), 3 1 1 3 16(CAACP) , 3 1 1 3 1 6 , (CAACAF) . 3 1 13 16(CAMP),  3 1 13 1 6(CAMAF), 3 11 3 1 6 (CKCAF).

Algorithm : 
    1. Initialize the Array array of size N with 0.
    2. array[0] = 1
    3. for i = 1 to N (N is length of given input string)
        a) If value of current single character is less than or equal to 26 Then
               array[i] = array[i-1]
        b) If value of current element and previous element is less than or equal to 26 Then
               array[i] += array[i-2]

Implementation:

class Alphacode{
static int ways(String input){
                //Boundary condition check
if(input == null || input.length() == 0)
return 0;

int []arr = new int[input.length() ];
arr[0] = 1;

for(int i = 1; i < input.length(); i++){
int singleDigit = input.charAt(i) - '0';  //check for single digit value
if(singleDigit  <= 26)
arr[i] = arr[i-1];

int doubleDigit = Integer.parseInt(input.substring(i-1, i+1));  //check for double digit value
if(doubleDigit  <= 26 )
if( i== 1)
arr[i] = arr[i-1]+1;
else
arr[i] += arr[i-2];

}
return arr[input.length()-1];
}

public static void main(String... args){
String input= "25114";
int ways = ways(input);
System.out.println(ways);
}
}

Bits required to convert integer A into integer B

Determine the number of bits required to convert integer A into integer B.
Ex:

Input :  integer A = 4, B = 2.
output : 2 bits

Solution:

int bitsRequired(int a, int b){
     int count = 0; //count of required bits
     int xor = a ^ b;
   
     for(int i = xor; i != 0; ){
          count += i & 1;
          i = i >> 1;
     }
     return count;
}

Find Missing Number In Given String

Given a string of numbers in sequence order. find the missing number.Range is not given. 
sample input:"9899100101103104105" 


Answer:102

Solution:


class FindMissingNumberInGivenString{
static int find(String str){
if(str == null || str.length() == 0)
return -1;

for(int i = 1; i < str.length()/2  ; i++){
int prevNum = getNumber(str, 0, i);
int offset = i;

while(true){
int nextA = prevNum + 1;
int lenA = getLength(nextA);
int nextB = prevNum + 2;
int lenB = getLength(nextB);

if(offset + lenA > str.length())
break;

int number = getNumber(str, offset, lenA);
if(number == nextA){
prevNum = nextA;
offset += lenA;
if(offset == str.length())
break;
continue;
}

if(offset + lenB > str.length())
break;

number = getNumber(str, offset, lenB);
if(number == nextB){  //found
return nextA;
}

break; //wrong sequence
}
}
return -1;
}

private static int getLength(int num) {
int len = 0;
while (num> 0){
num /= 10;
len++;
}
return len;
}

static int getNumber(String str, int i, int j){
return Integer.parseInt(str.substring(i, i+j));
}

public static void main(String ... args){
String str = "9899100101103";
System.out.println(find(str));
  }
}

Write a method to determine if two strings are anagrams of each other

Write a method to determine if two strings are anagrams of each other.

e.g. isAnagram(“secure”, “rescue”) → true
e.g. isAnagram(“conifers”, “fircones”) → true 
e.g. isAnagram(“google”, “facebook”) → false

Solution:

boolean isAnagram(String str, String str2){
      if(str == null && str2 == null)
             return true;

      if(str == null || str2 == null)
             return false;

      if(str.length() != str2.length())
             return false;

      int []count = new int[256];

      //count the occurrence of characters in given string "str".   
      for(int i = 0; i < str.length(); i++){
            int c = str.charAt(i);
            count[c]++;
      } 
     
     for(int i = 0; i < str2.length(); i++){
             int ch = str2.charAt(i);
             if(--count[ch] < 0)
                   return false;
     }  
     return true;  
}

Rearrange an array using swap with 0

You have two arrays src, tgt, containing two permutations of the numbers 0..n-1. You would like to rearrange src so that it equals tgt.

The only allowed operations is “swap a number with 0”, e.g. {1,0,2,3} -> {1,3,2,0} (“swap 3 with 0”). Write a program that prints to stdout the list of required operations.

Solution:

class RearrangeArrayUsingSwapWithZero{
static void arrange(int []src, int []target){
if(src == null || target == null)
return;

for(int i = 0; i < src.length; i++){
if(src[i] != target[i] && target[i] != 0){
int indexOfZero = findIndex(src, 0);
swap(src, indexOfZero, i);
int idx = findIndex(src, target[i]);
swap(src, i, idx);
System.out.println("swap "+target[i] +"with 0");
}
}
}

/*function to find the index of given number in the array*/
static int findIndex(int[]arr, int n){
for(int i = 0; i < arr.length; i++){
if(arr[i] == n)
return i;
}
return -1;
}

/*Utility function to swap array elements*/
static void swap(int []arr, int i, int j){
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}

public static void main(String... args){
                /*Test Case - 1*/
int []src = {1,0,2,3};
int []target = {1,3,2,0};
arrange(src, target);

                /*Test Case - 2*/
int []src1 = {1,0,2,3};
                int []target1 = {0,2,3,1};
arrange(src1, target1);
}
  }

Selection Rank Algorithm

Selection Rank is a well known algorithm in computer science to find the ith smallest (or largest) element in an array in expected linear time.

The basic algorithm for finding the ith smallest elements goes like this:
»»Pick a random element in the array and use it as a ‘pivot’. Move all elements smaller than that element to one side of the array, and all elements larger to the other side.
»»If there are exactly i elements on the right, then you just find the smallest element on that side.
»»Otherwise, if the right side is bigger than i, repeat the algorithm on the right. If the right side is smaller than i, repeat the algorithm on the left for i – right.size().

Given this algorithm, you can either:
»»Tweak it to use the existing partitions to find the largest i elements (where i = one million).
»»Or, once you find the ith largest element, run through the array again to return all elements greater than or equal to it.

This algorithm has expected O(n) time.

class SelectionRankAlgorithm{
public static int rank(int []a, int left, int right, int rank){
int random = random(left, right);   //random number
int pivot = a[random];

/* partition and return end of left partition */
int leftEnd = partition(a, left, right, pivot);

int leftSize = leftEnd - left + 1;
if(leftSize == rank+1)
return Math.max(a[left] , a[leftEnd]);
else if(rank < leftSize)
return rank(a, left, leftEnd, rank);
else
return rank(a, leftEnd + 1, right, rank - leftSize);
}

public static int partition(int []a, int left, int right, int pivot){
while(true){
while(left<=right && a[left]<= pivot)
left++;

while(left<=right && a[right]>pivot)
right--;

if(left > right)
return left - 1;

swap(a, left, right);
}
}

//Utility Function to generate the random number
public static int random(int lower, int higher){
return (int)(Math.random()*(higher - lower)) + lower;
}

public static void swap(int []a, int left, int right){
int temp = a[left];
a[left] = a[right];
a[right] = temp;
}

//main method
public static void main(String... args){
int []a = {1,3,4,2,10,9,7,8,0,5,};
int min = rank(a, 0, a.length - 1, 3);
System.out.println(min);
}
}

Check if a binary tree is a binary search tree

Implement a function to check if a binary tree is a binary search tree.

For binary search tree click here

Solution:

boolean isBST(TreeNode root){
      if(root == null)
            return true;

     return isBSTHelper(root, Integer.MIN_VALUE, Integer.MAX_VALUE);
}

boolean isBSTHelper(TreeNode root, int min, int max){
     if(root == null)
            return true;

     if(root.data > max || root.data <= min)
            return false;

     if( !isBSTHelper(root.left, min, root.data) || !isBSTHelper(root.right, root.data, max))
            return false;

     return true;
}

Time Complexity : O(N)
Space Complexity : O(logN)

Check whether given array can be grouped in sets of pairs such that sum of each pair is divisible by K.

Given array of ints. Assuming total no. of elements is even. Need to tell whether this array can be grouped in sets of pairs such that sum of each pair is divisible by K.
eg: 0,2,4,8,12,20,18,4 and k=4
so (0,8), (2,18), (4,20), (4,12) is one such set in which sum of each pair is divisible by k. 

Solution:


class Solution{
static boolean find(int []arr, int k){
if(arr == null || arr.length == 0)
return false;

int len = arr.length;
if(len % 2 != 0)
return false;

int count= 0;
for(int i = 0; i < len; i++){
for(int j = i+1; j < len; j++){
if(arr[j] != -1){
int t = arr[i] + arr[j];
if(t %k == 0){
count++;
arr[j]=-1;
break;
}
}
}
}
return (count == len/2);
}

public static void main(String... args){
int []arr = {0,2,4,8,12,20,18,4};
int k =4;
System.out.println(find(arr,k));
  }
  }

Print Coordinate of all Tree nodes

Given a Binary Tree. Assuming each node denotes some x,y coordinate. root node denotes (0,0). Write a code to display coordinate of all nodes.

For example, let us consider the below tree:

Output: Coordinate of 4 : (0,0), Coordinate of 2 : (-1,-1), Coordinate of 3 : (1,-1), Coordinate of 1 : (-2,-2), Coordinate of 3 : (0,-2) etc.

Solution:

class CoordinatesOfTree{
static class Tree{
int data;
Tree left = null;
Tree right = null;

public Tree(int data){
this.data = data;
}

//create minimal bst
public static Tree createBST(int []a, int left, int right){
if(right < left)
return null;

int mid = (left + right)/2;
Tree root = new Tree(a[mid]);
root.left = createBST(a, left, mid - 1);
root.right = createBST(a, mid + 1, right);

return root;
}
}

static void printCoordinate(Tree root,int x, int y){
if(root == null)
return;

System.out.println(root.data +" : ("+x+","+y+")");
printCoordinate(root.left, x-1, y-1);
printCoordinate(root.right, x+1,y-1);
}

public static void main(String... args){
int[]arr = {1,2,3,4,5,6,7};
Tree root = Tree.createBST(arr, 0,arr.length-1);
printCoordinate(root,0, 0);
}
 }

Bunny Ears

We have bunnies standing in a line, numbered 1, 2, ... The odd bunnies (1, 3, ..) have the normal 2 ears. The even bunnies (2, 4, ..) we'll say have 3 ears, because they each have a raised foot. Recursively return the number of "ears" in the bunny line 1, 2, ... n (without loops or multiplication). 

bunnyEars2(0) → 0
bunnyEars2(1) → 2
bunnyEars2(2) → 5

Solution:


public int bunnyEars2(int bunnies) {
  /*Base condition*/
  if(bunnies == 0)
     return 0;
  
  /*For odd bunnies*/
  if(bunnies% 2== 0)
     return bunnyEars2(bunnies-1) + 3;
  else  /*For even bunnies*/
     return bunnyEars2(bunnies-1) + 2;
}

Group Sum

Given an array of ints, is it possible to choose a group of some of the ints, such that the group sums to the given target?

Example:

Input : arr[] = {2, 4, 8}, target = 10
Output : true.(because 2+ 8 = 10(target sum))

Input : arr[] = {2, 4, 8}, target = 9
Output : false.(because we can't achieve target sum by any combination of array elements) 


Solution:

boolean isGroupSum(int start, int []arr, int target){
      /*Base condition*/
      if(start >= arr.length)
           return (target == 0);

      /*we found the target sum, return true*/
      if(target == 0)
           return true;
      
      /*else, check if sum can be obtained by any of the following
            1) Including the current element
            2) Excluding the current element*/
      return isGroupSum(start+1, arr, target - arr[start]) 
               || isGroupSum(start+1, arr, target);
}