Problem Statement
Write a function ‘howSum(targetSum, numbers)’ that takes in a targetSum and an array of number as an arguments.
The function should return an array containing any combination of elements that add up to exactly the targetSum.
If there is no combination that adds up to the targetSum, then return null
If there are multiple combination possible, you may return any single one.
Solution
package com.techbruiser.recursion;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
/**
* Write a function 'howSum(targetSum, numbers)' that takes in a targetSum and an array of number as an arguments.
*
* The function should return an array containing any combination of elements that add up to exactly the targetSum.
* If there is no combination that adds up to the targetSum, then return null
*
* If there are multiple combination possible, you may return any single one.
*
* @author Lenovo-PC
*
*/
public class HowSum {
public static void main(String[] args) {
System.out.println("howSum(7, [2,3]" + howSum(7, Arrays.asList(2,3)));//[3,2,2]
memorization.clear();
System.out.println("howSum(7, [5,3,4,7]" + howSum(7, Arrays.asList(5,3,4,7)));//[4,3]
memorization.clear();
System.out.println("howSum(7, [2,4]" + howSum(7, Arrays.asList(2,4)));//null
memorization.clear();
System.out.println("howSum(8, [2,3,5]" + howSum(8, Arrays.asList(2,3,5)));//[2,2,2,2]
memorization.clear();
System.out.println("howSum(300, [7,14]" + howSum(300, Arrays.asList(7,14)));//null
}
/**
* Approach-1 Without Memorization
* @param targetSum
* @param numbers
* @return
*/
/*static List<Integer> howSum(int targetSum, List<Integer> numbers) {
if(targetSum == 0) {
return new ArrayList<>();
}
if(targetSum < 0) {
return null;
}
for(Integer number : numbers) {
int remainder = targetSum - number;
List<Integer> remainderResult = howSum(remainder, numbers);
if(remainderResult != null) {
remainderResult.add(number);
return remainderResult;
}
}
return null;
}*/
/**
* Approach-2 With Memorization
* @param targetSum
* @param numbers
* @return
*/
static Map<Integer, List<Integer>> memorization = new HashMap<>();
static List<Integer> howSum(int targetSum, List<Integer> numbers) {
if(memorization.containsKey(targetSum)) {
return memorization.get(targetSum);
}
if(targetSum == 0) {
return new ArrayList<>();
}
if(targetSum < 0) {
return null;
}
for(Integer number : numbers) {
int remainder = targetSum - number;
List<Integer> remainderResult = howSum(remainder, numbers);
if(remainderResult != null) {
remainderResult.add(number);
memorization.put(targetSum, remainderResult);
return memorization.get(targetSum);
}
}
memorization.put(targetSum, null);
return null;
}
}