title: How to find if a subarray has a specific sum inside a 2D array in Java ?
body: <p>I am trying to solve a Image matching problem by comparing the average color of pixels present in both the source and pattern image. I have reduced this problem to a sub array sum problem, but cannot figure out a way to solve it.</p>
  <p>Lets say i have a 2D array ARR with all positive integers. I have a number x( which is the average of the pixel colors present in a small pattern image). I just need to find any subarray in ARR which has the exact sum x. I found a similar problem which could be solved with Dynamic programming here.</p>
  <p><a href="http://www.geeksforgeeks.org/dynamic-programming-set-27-max-sum-rectangle-in-a-2d-matrix/" rel="noreferrer">http://www.geeksforgeeks.org/dynamic-programming-set-27-max-sum-rectangle-in-a-2d-matrix/</a></p>
  <p>But that talks about finding a subarray with <strong>maximum sum</strong> and not the sum which was already given.</p>
  <pre>
  So if this the given array.
  
  3   4   8   9   3
  2   10  4   2   1
  8   1   4   8   0
  3   5   2   12  3
  8   1   1   2   2
  
  And if the given sum is 19, then it should return this window
  
  3   4   8   9   3
  2   <b>10  4</b>   2   1
  8   <b>1   4</b>   8   0
  3   5   2   12  3
  8   1   1   2   2
  
  And if the given sum is 23, then it should return this window
  
  3   4   8   <b>9   3</b>
  2   10  4   <b>2   1</b>
  8   1   4   <b>8   0</b>
  3   5   2   12  3
  8   1   1   2   2
      
  </pre>
  <p>How can i find this efficiently ? Can Dynamic Programming be used here ? Please help me out here.</p>