Any numbers sum up to k iterative

Problem

Given an integer array and a number k. Find out whether it is possible to have a sum k by using any number of numbers from the array.

Solution

We solve this by dynamic programming. In an iterative bottom up approach. Suppose we have a two dimensional boolean array named memo. Where memo [i][j] is true if the sum j is possible by using array elements less than i. So if i=0, that means no array element is being used for calculating the sum. So memo[0][j] is always false; now we have two for loops one for the array elements and one for the weights. In every step of the iteration our problem depends on the previous subproblem. Suppose our array element is 3 and required sum is 5. There might be two cases, this element 3 is either included in the solution or not. If it is included then we need to find whether the sum 2 is possible with the elements before it. If it is not included then we need to find whether the sum 5 is possible with the elements before it. If any one of these two results are true then the sum 5 is possible with the array elements upto that point. So our final result will be memo[array length][given k]. As this value will depend on the previous array elements, we start from 0,0 and progress from there. As all elements are integer, the value of k can vary from 0 to k in steps of 1.

Code

public class AnyNumberSumUptoK
{

 public static void main(String[] args)
 {
  int[]arr={4,6,2,8};
  System.out.println(isSumPossible(arr,22));
 }

 public static boolean isSumPossible(int[] arr, int k)
 {
  boolean[][] memo=new boolean[arr.length+1][k+1];
  for(int i=1;i<=arr.length;++i)
  {
   for(int w=1;w<=k;++w)
   {
    if(w==arr[i-1])
     memo[i][w]=true;
    else if(w>arr[i-1])
     memo[i][w]=memo[i-1][w]||memo[i-1][w-arr[i-1]];
    else
     memo[i][w]=memo[i-1][w];
   }
  }
  return memo[arr.length][k];
 }
}