CanSum Solution in Java

Problem Statement

Write a function ‘canSum(targetSum, numbers)’ that takes in a targetSum and an array of numbers as arguments.

The function should return a boolean indicating whether or not it is possible to generate the targetSum using numbers from the array.

You may use an element of the array as many times as needed.

You may assume that all input numbers are nonnegative.

Solution

package com.techbruiser.recursion;

import java.util.HashMap;
import java.util.Map;

/**
 *  
 */
public class CanSum {

	public static void main(String[] args) {
		System.out.println("canSum(7, [2,3]) " + canSum(7, new int[] {2,3}));//true
		memorization.clear();
		System.out.println("canSum(7, [5,3,4,7]) " + canSum(7, new int[] {5,3,4,7}));//true
		memorization.clear();
		System.out.println("canSum(7, [2,4]) " + canSum(7, new int[] {2,4}));//false
		memorization.clear();
		System.out.println("canSum(7, [2,3,5]) " + canSum(7, new int[] {2,3,5}));//true
		memorization.clear();
		System.out.println("canSum(7, [7,14]) " + canSum(7, new int[] {7,14}));//true
		memorization.clear();
		System.out.println("canSum(300, [7,14]) " + canSum(300, new int[] {7,14}));//false
	}
	
	
	/**
	 * Approach-1 Without Memorization
	 */
	 /*static boolean canSum(int targetSum, int[] numbers) {
		if(targetSum == 0) {
			return true;
		}
		if(targetSum < 0) {
			return false;
		}
		for(int i=0;i<numbers.length;i++) {
			int remainderSum = targetSum-numbers[i];
			
			if(canSum(remainderSum, numbers)) {
				return true;
			}
		}
		return false;
	}*/
	
	
	/**
	 * Approach-2 With Memorization
	 */
	static Map<Integer, Boolean> memorization = new HashMap<>();
	static boolean canSum(int targetSum, int[] numbers) {
		if(memorization.containsKey(targetSum)) {
			return memorization.get(targetSum);
		}
		if(targetSum == 0) {
			return true;
		}
		if(targetSum < 0) {
			return false;
		}
		for(int i=0;i<numbers.length;i++) {
			int remainderSum = targetSum-numbers[i];
			boolean tempResult = canSum(remainderSum, numbers);
			memorization.put(targetSum, tempResult);
			if(tempResult) {
				return true;
			}
		}
		memorization.put(targetSum, false);
		return false;
	}
	
	

}