Wednesday, March 22, 2023
HomeSoftware DevelopmentVariety of subsequences of an array with given operate worth

Variety of subsequences of an array with given operate worth

Enhance Article

Save Article

Like Article

Enhance Article

Save Article

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.


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 = 2

Enter: 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:


#embrace <bits/stdc++.h>

utilizing namespace std;


int dp[101][101][1001];


int countValue(int n, int F, vector<int> v)




    dp[0][0][0] = 1;



    for (int i = 0; i < n; i++) {

        for (int okay = 0; okay < n; okay++) {

            for (int s = 0; s <= 1000; s++) {

                lengthy lengthy sq

                    = (lengthy lengthy)v[i] * (lengthy lengthy)v[i];





                dp[i + 1][k + 1][s + sq] += dp[i][k][s];



                dp[i + 1][k][s] += dp[i][k][s];





    int cnt = 0;



    for (int j = 1; j <= n; j++) {

        cnt += dp[n][j][F * j];




    return cnt;



int essential()


    vector<int> v = { 1, 2, 1, 2 };

    int F = 2, N = v.dimension();



    cout << countValue(N, F, v);

    return 0;


Time Complexity: O(F*N2)
Auxilairy House: O(F*N2)



Please enter your comment!
Please enter your name here

twenty − thirteen =

Most Popular

Recent Comments