Any numbers sum up to k recursive

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 will apply dynamic programming to solve this problem. Let us have a function func(index,sum) which gives us true if the sum is possible by adding any number from an array using numbers starting from index till the end. So func(0,k) means whether the sum k is possible by using all the elements of the given array. So this is our original problem. So we need to find out func(0,k). In this function we try to decide whether the number at the index position is required to make the sum k or not. If it is needed that means we need to make the number k-arr[index] with the remaining numbers to its right side. If it is not needed that means we need to make the number k with the remaining numbers. If any one of this is true that means it is possible to have k as a sum with the elements of the array. In this solution we take a recursive approach, that is we start from func(0,n) and recursively call the other functions in top down approach. We fill the memo array to reuse the value of a function so that for next iteration with the same values the function doesn't need to recompute. So this way we span from top to bottom and then fill the array from bottom to top to produce the final result. There is another approach which is iterative and don't need recursion where we directly fill the array from bottom to top. We will discuss that in our next page.

Code

public class AnyNumberSumUptoKRecursive
{
 public static void main(String[] args)
 {
  int [] arr={3,5,6,2};
  System.out.println(isSumPossible(arr, 13));
 }
 
 public static boolean isSumPossible(int[]arr, int k)
 {
  Boolean [][]memo=new Boolean[arr.length+1][k+1];
  return isSumPossible(memo,arr,0,k);
 }
 
 private static boolean isSumPossible(
  Boolean[][]memo, 
  int[]arr,int i,int k)
 {
  if(memo[i][k]!=null)
   return memo[i][k];
  if(i==arr.length-1)
  {
   if(arr[i]==k||k==0)
    return true;
   else
    return false;
  }
  if(arr[i]>k)
  {
   memo[i][k]=isSumPossible(memo,arr,i+1,k);
   return memo[i][k];
  }
  memo[i][k]=isSumPossible(memo,arr,i+1,k-arr[i])||
   isSumPossible(memo,arr, i+1, k);
  return memo[i][k];
 }

}