Given an array A[] of size N and integer F, the duty is to seek out the quantity of subsequences the place the common of the sum of the sq. of parts (of that individual subsequence) is the same as the worth F.
Examples:
Enter: A[] = {1, 2, 1, 2}, F = 2
Output: 2
Clarification: Two subsets with worth F = 2 are {2} and {2}. The place 2^2/1 = 2Enter: A[] = {1, 1, 1, 1}, F = 1
Output: 15
Clarification: All of the subsets will return the operate worth of 1 besides the empty subset. Therefore the whole variety of subsequences will likely be 2 ^ 4 – 1 = 15.
Strategy: This may be solved utilizing the next thought:
Utilizing Dynamic programming, we are able to scale back the overlapping of subsets which can be already computed.
Comply with the steps under to unravel the issue:
- Initialize a 3D array, say dp[][][], the place dp[i][k][f] signifies the variety of methods to pick okay integers from first i values such that their sum of squares or every other operate in keeping with F is saved in dp[i][k][f]
- Traverse the array, we nonetheless have 2 choices for every component i.e. to embrace or to exclude. The transition will likely be as proven on the finish:
- If included then we can have okay + 1 parts with purposeful sum worth equal to s+ Â sq the place sq is the sq. worth i.e. arr[i]^2.
- Whether it is excluded we merely traverse to the subsequent index storing the earlier state in it as it’s.
- Lastly, the reply would be the sum of dp[N][j][F*j] because the purposeful worth is the squared sum common.
Transitions for DP:
- Embody the ith component: dp[i + 1][k + 1][s + sq] += dp[i][k][s]
- Exclude the ith component: dp[i + 1][k][s] += dp[i][k][s]
Under is the implementation of the code:
C++
|
|
Time Complexity:Â O(F*N2)
Auxilairy House:Â O(F*N2)
