CC-10 : Find number combinations with required sum.
Description:
Given an input array of numbers N, and input integer requiredSum, find all combinations of numbers from input array that sum up to requiredSum. Note: numbers in array can be duplicated to sum up to required number.
Test cases and expected outputs:
| Input Parameters |
Expected outputs |
| arr= {1,2,4};
|
Number combinations with sum 4:
1,1,1,1
1,1,2
2,2
4
|
Pseudocode:
getCombinationsWithSum(n):
| Initialize ArrayList of ArrayList of Integers named combinations.
|
| Initialize ArrayList of integers named currCombi.
|
| Initialize variable idx to 0.
|
| Call getCombinationsWithSumRecursive(
arr,reqSum,idx,combinations,currCombi).
|
getCombinationsWithSumRecursive(
arr,reqSum,idx,combinations,currCombi):
| If reqSum is 0:
Add currCombi to combinations.
return.
|
| If reqSum < 0 or idx > arr.length :
Return.
|
| CurrCombi.add(arr[idx].
|
| Recursively call getCombinationsWithSumRecursive(arr,reqSum-arr[idx],idx,combinations,currCombi).
|
| Remove last number from currCombi.
|
| Recursively call getCombinationsWithSumRecursive(arr,reqSum-arr[idx],idx+1,combinations,currCombi).
|
Code:
public ArrayList<ArrayList<Integer>> getCombinationsWithSum(int[] arr,int reqSum){
ArrayList<ArrayList<Integer>> combinations=new ArrayList<ArrayList<Integer>>();
ArrayList<Integer> currCombi=new ArrayList<Integer>();
int idx=0;
getCombinationsWithSumRecursive(arr, reqSum, idx, combinations,currCombi);
return combinations;
}
public void getCombinationsWithSumRecursive(int[] arr, int reqSum, int idx,
ArrayList<ArrayList<Integer>> combinations,ArrayList<Integer> currCombi) {
if (reqSum==0) {
combinations.add(new ArrayList<Integer>(currCombi));
return;
} else {
if (reqSum < 0 || idx >=arr.length) {
return;
} else {
currCombi.add(arr[idx]);
getCombinationsWithSumRecursive(arr, reqSum-arr[idx], idx, combinations,currCombi);
currCombi.remove(currCombi.size()-1);
getCombinationsWithSumRecursive(arr, reqSum, idx+1, combinations,currCombi);
}
}
}
Click here to download and run code and test cases !
Below fully running code can be copied and run on Eclipse or other Java IDEs. Refer the classname in code below. If the class name below is "A", save the code below to a file named A.java before running it.
Be sure to try your own test cases to enhance your understanding !
You can also tweak the code to optimize or add enhancements and custom features.
import java.util.ArrayList;
public class RecursionGetCombinationsWithSum {
public ArrayList<ArrayList<Integer>> getCombinationsWithSum(int[] arr,int reqSum){
ArrayList<ArrayList<Integer>> combinations=new ArrayList<ArrayList<Integer>>();
ArrayList<Integer> currCombi=new ArrayList<Integer>();
int idx=0;
getCombinationsWithSumRecursive(arr, reqSum, idx, combinations,currCombi);
return combinations;
}
public void getCombinationsWithSumRecursive(int[] arr, int reqSum, int idx,
ArrayList<ArrayList<Integer>> combinations,ArrayList<Integer> currCombi) {
if (reqSum==0) {
combinations.add(new ArrayList<Integer>(currCombi));
return;
} else {
if (reqSum < 0 || idx >=arr.length) {
return;
} else {
currCombi.add(arr[idx]);
getCombinationsWithSumRecursive(arr, reqSum-arr[idx], idx, combinations,currCombi);
currCombi.remove(currCombi.size()-1);
getCombinationsWithSumRecursive(arr, reqSum, idx+1, combinations,currCombi);
}
}
}
public static void printArrayListSummary(ArrayList al, String label) throws Exception {
if (al == null) { System.out.println("\n\n Input ArrayList was null !! \n"); return; }
System.out.println();
System.out.println("***********************************************************************");
System.out.print(label+" : ");
int arrayIndex=0;
for (arrayIndex=0; arrayIndex < al.size(); arrayIndex++) {
System.out.print(al.get(arrayIndex));
if (arrayIndex < al.size()-1) {System.out.print(",");}
}
System.out.println();
System.out.println("************************************************************************");
System.out.println();
Thread.sleep(2000);
return;
}
public static void main(String[] args) {
ArrayList<ArrayList<Integer>> retVal;
try {
RecursionGetCombinationsWithSum rcn=new RecursionGetCombinationsWithSum();
int[] arr= {1,2,4};
int reqSum=4;
retVal=rcn.getCombinationsWithSum(arr, 4);
System.out.print("NumberCombinations with sum "+reqSum);
for (int idx=0; idx < retVal.size(); idx++) {
printArrayListSummary(retVal.get(idx), "");
}
}catch (Exception exception) {
System.out.print("Exception: "+ exception);
exception.printStackTrace();
}
}
}