ArraySumEqualsTarget

Find how many combinations are present in the given array which when summed, equals the given target value.

package abc;

 

import java.util.Arrays;

 

public class SumSubArray {

 

       public static void main(String[] args) {

        //find how many combinations are present in the array with sum = target

        //This problem is taken from LeetCode

//Solution

        //sum each index value from left to right.

        //summed value at an index x as we progress from left to right = x1

        //Let’s say x1-target = y1, the value at one of the previous index y

        //Then the target value is the sum of the values from index y+1 to x , count this

        //OR if x>=y and x1-target = 0, count this also

 

        //suppose y1 is at index 8 and x1 is at index 6, and x1-target=y1, then sum of the index values of 7, 8 = target value

             int target = 9;

             int[] num = {9,2,5,3,1,0,3,9,3,-4,1,2,1,4};

            

             int l = num.length;

             int[] sumAtindex = new int[l];

             int sumValues = 0;

             for(int i=0; i<l; i++) {

                    sumValues = sumValues+num[i];

                    sumAtindex[i] = sumValues;

             }

             System.out.println("Array with sum "+Arrays.toString(sumAtindex));//Array with sum [9, 11, 16, 19, 20, 20, 23, 32, 35, 31, 32, 34, 35, 39]

             int count = 0;

            

             //Find the count

             for(int i=0; i<l; i++) {

                    for(int j=0; j<l; j++) {

                           if(i>=j)

                           if((sumAtindex[i]-target==sumAtindex[j])||(sumAtindex[i]-target==0)) {

                                 count++;

                                 System.out.println("the indexValues are =  "+sumAtindex[i]+" "+sumAtindex[j]);

                           }

                    }

             }

             System.out.println("count =  "+count);//5

       }

}

 

Output:

Array with sum [9, 11, 16, 19, 20, 20, 23, 32, 35, 31, 32, 34, 35, 39]

the indexValues are =  9 9

the indexValues are =  20 11

the indexValues are =  20 11

the indexValues are =  32 23

the indexValues are =  32 23

count =  5