You are given a set of candidates (without duplicates) and a target number (target), you have to find all unique combinations in candidates where the candidate numbers sum to target.
The same repeated number may be chosen from candidates the unlimited number of times.
We will solve this question using the dynamic programming approach.
public class CombinationSumSetCount {
public static void main(String[] args) {
int[] arr = new int[] {2, 3, 5};
int target = 8;
System.out.println(CalculateSet(arr, target));
}
private static int CalculateSet(int[] arr, int target) {
int[][] sum = new int[arr.length][target+1];
for(int i=0;i<arr.length;i++) {
for(int j=0;j<target+1;j++) {
if(j==0)
sum[i][j] = 1;
else if( i == 0)
sum[i][j] = j % arr[i] == 0 ? 1 : 0;
else if( j < arr[i])
sum[i][j] = sum[i-1][j];
else
sum[i][j]= sum[i-1][j] + sum[i][j-arr[i]];
}
}
return sum[arr.length-1][target];
}
}
Output :
3
