Q : Count all subset of given array that sum up to target value.
Ex: N = 4, arr[] = {1,2,3,3} , sum = 6
Output : 3
Explanation : 3 possible subsets that sum up to value as 6 are
{1,2,3}, {3,3} and {1,2,3}
Taking both 3 as differently
I provided backtracking solution but when looking for solution it seems DP / 0-1 knapsack problem.
Why backtrack not work here ??
If following is wrong solution ??
Please suggest
class Solution{
int res = 0;
public int perfectSum(int arr[],int n, int sum)
{
// Your code goes here
backtrack(arr, n, sum, 0);
return res;
}
public void backtrack(int[] arr, int n, int sum, int start) {
if(sum == 0) {
res++;
return;
}
if(sum < 0) {
return;
}
for(int i=start;i<n;i++) {
sum = sum-arr[i];
backtrack(arr, n, sum, i+1);
sum = sum+arr[i];
}
}
}
Comments (2)