Number of subsequences of an array with given function value

19 June 2025

4

Given an array A[] of length N and integer F, the task is to find the number of subsequences where the average of the sum of the square of elements (of that particular subsequence) is equal to the value F.

Examples:

Input: A[] = {1, 2, 1, 2}, F = 2
Output: 2
Explanation: Two subsets with value F = 2 are {2} and {2}. Where 2^2/1 = 2

Input: A[] = {1, 1, 1, 1}, F = 1
Output: 15
Explanation: All the subsets will return the function value of 1 except the empty subset. Hence the total number of subsequences will be 2 ^ 4 – 1 = 15.

Approach: This can be solved using the following idea:

Using Dynamic programming, we can reduce the overlapping of subsets that are already computed.

Follow the steps below to solve the problem:

Initialize a 3D array, say dp[][][], where dp[i][k][f] indicates the number of ways to select k integers from first i values such that their sum of squares or any other function according to F is stored in dp[i][k][f]
Traverse the array, we still have 2 options for each element i.e. to include or to exclude. The transition will be as shown at the end:
If included then we will have k + 1 elements with functional sum value equal to s+ sq where sq is the square value i.e. arr[i]^2.
If it is excluded we simply traverse to the next index storing the previous state in it as it is.
Finally, the answer will be the sum of dp[N][j][F*j] as the functional value is the squared sum average.

Transitions for DP:

Include the ith element: dp[i + 1][k + 1][s + sq] += dp[i][k][s]

Exclude the ith element: dp[i + 1][k][s] += dp[i][k][s]

Below is the implementation of the code:

C++

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Storing the DP states
// dp[i][k][f] indicates that the number
// of ways to select k integers from first
// i values such that their sum of squares
// or any other function according to F
// is stored in dp[i][k][F]
int dp[101][101][1001];
 
// Calculate the number of subsequences
// with given function value
int countValue(int n, int F, vector<int> v)
{
 
    // Base condition
    dp[0][0][0] = 1;
 
    // Three loops for three states
    for (int i = 0; i < n; i++) {
        for (int k = 0; k < n; k++) {
            for (int s = 0; s <= 1000; s++) {
                long long sq
                    = (long long)v[i] * (long long)v[i];
 
                // Recurrence relation
 
                // Include the ith element
                dp[i + 1][k + 1][s + sq] += dp[i][k][s];
 
                // Exclude the ith element
                dp[i + 1][k][s] += dp[i][k][s];
            }
        }
    }
 
    int cnt = 0;
 
    // Iterate over the range [1, N]
    for (int j = 1; j <= n; j++) {
        cnt += dp[n][j][F * j];
    }
 
    // Return the final count
    return cnt;
}
 
// Driver Code
int main()
{
    vector<int> v = { 1, 2, 1, 2 };
    int F = 2, N = v.size();
 
    // Function call
    cout << countValue(N, F, v);
    return 0;
}

Java

import java.util.*;
 
public class Main {
    // Storing the DP states
    // dp[i][k][f] indicates that the number
    // of ways to select k integers from first
    // i values such that their sum of squares
    // or any other function according to F
    // is stored in dp[i][k][F]
    static long[][][] dp = new long[101][101][1001];
 
    // Calculate the number of subsequences
    // with given function value
    static long countValue(int n, int F, List<Integer> v) {
 
        // Base condition
        dp[0][0][0] = 1;
 
        // Three loops for three states
        for (int i = 0; i < n; i++) {
            for (int k = 0; k < n; k++) {
                for (int s = 0; s <= 1000; s++) {
                    long sq = (long) v.get(i) * (long) v.get(i);
 
                    // Recurrence relation
 
                    // Include the ith element
                    if (i + 1 <= n && k + 1 <= n && s + sq <= 1000) {
                        dp[i + 1][k + 1][s + (int) sq] += dp[i][k][s];
                    }
 
                    // Exclude the ith element
                    if (i + 1 <= n && k <= n && s <= 1000) {
                        dp[i + 1][k][s] += dp[i][k][s];
                    }
                }
            }
        }
 
        long cnt = 0;
 
        // Iterate over the range [1, N]
        for (int j = 1; j <= n; j++) {
            if (n <= 100 && j <= 100 && F * j <= 1000) {
                cnt += dp[n][j][F * j];
            }
        }
 
        // Return the final count
        return cnt;
    }
 
    // Driver code
    public static void main(String[] args) {
        List<Integer> v = Arrays.asList(1, 2, 1, 2);
        int F = 2, N = v.size();
 
        // Function call
        System.out.println(countValue(N, F, v));
    }
}

Python3

# Python program for the above approach
 
# Storing the DP states
# dp[i][k][f] indicates that the number
# of ways to select k integers from first
# i values such that their sum of squares
# or any other function according to F
# is stored in dp[i][k][F]
dp = [[[0 for i in range(1005)] for j in range(101)] for k in range(101)]
 
# Calculate the number of subsequences
# with given function value
def countValue(n, F, v):
 
    # Base condition
    dp[0][0][0] = 1
 
    # Three loops for three states
    for i in range(n):
        for k in range(n):
            for s in range(1001):
                sq = v[i] * v[i]
 
                # Recurrence relation
 
                # Include the ith element
                dp[i + 1][k + 1][s + sq] += dp[i][k][s]
 
                # Exclude the ith element
                dp[i + 1][k][s] += dp[i][k][s]
 
    cnt = 0
 
    # Iterate over the range [1, N]
    for j in range(1, n + 1):
        cnt += dp[n][j][F * j]
 
    # Return the final count
    return cnt
 
# Driver Code
if __name__ == '__main__':
    v = [1, 2, 1, 2]
    F, N = 2, len(v)
 
    # Function call
    print(countValue(N, F, v))
 
# This code is contributed by Susobhan Akhuil

C#

// C# program for the above approach
 
using System;
 
public class GFG {
    // Storing the DP states
    // dp[i][k][f] indicates that the number
    // of ways to select k integers from first
    // i values such that their sum of squares
    // or any other function according to F
    // is stored in dp[i][k][F]
    static int[,,] dp = new int[101,101,1005];
 
    // Calculate the number of subsequences
    // with given function value
    static int countValue(int n, int F, int[] v) {
 
        // Base condition
        dp[0,0,0] = 1;
 
        // Three loops for three states
        for (int i = 0; i < n; i++) {
            for (int k = 0; k < n; k++) {
                for (int s = 0; s <= 1000; s++) {
                    long sq = (long)v[i] * (long)v[i];
 
                    // Recurrence relation
 
                    // Include the ith element
                    dp[i + 1,k + 1,s + sq] += dp[i,k,s];
 
                    // Exclude the ith element
                    dp[i + 1,k,s] += dp[i,k,s];
                }
            }
        }
 
        int cnt = 0;
 
        // Iterate over the range [1, N]
        for (int j = 1; j <= n; j++) {
            cnt += dp[n,j,F * j];
        }
 
        // Return the final count
        return cnt;
    }
 
    // Driver Code
    public static void Main() {
        int[] v = { 1, 2, 1, 2 };
        int F = 2, N = v.Length;
 
        // Function call
        Console.WriteLine(countValue(N, F, v));
    }
}

Javascript

// Storing the DP states
// dp[i][k][f] indicates that the number
// of ways to select k integers from first
// i values such that their sum of squares
// or any other function according to F
// is stored in dp[i][k][F]
const dp = Array.from(Array(101), () => Array.from(Array(101), () => new Array(1005).fill(0)));
 
// Calculate the number of subsequences
// with given function value
function countValue(n, F, v) {
 
    // Base condition
    dp[0][0][0] = 1;
 
    // Three loops for three states
    for (let i = 0; i < n; i++) {
        for (let k = 0; k < n; k++) {
            for (let s = 0; s <= 1000; s++) {
                const sq = v[i] * v[i];
 
                // Recurrence relation
 
                // Include the ith element
                dp[i + 1][k + 1][s + sq] += dp[i][k][s];
 
                // Exclude the ith element
                dp[i + 1][k][s] += dp[i][k][s];
            }
        }
    }
 
    let cnt = 0;
 
    // Iterate over the range [1, N]
    for (let j = 1; j <= n; j++) {
        cnt += dp[n][j][F * j];
    }
 
    // Return the final count
    return cnt;
}
 
// Driver Code
const v = [1, 2, 1, 2];
const F = 2;
const N = v.length;
 
// Function call
console.log(countValue(N, F, v));

Output

Time Complexity: O(F*N²)
Auxiliary Space: O(F*N²)

Efficient approach : Space optimization

In previous approach the current value dp[i][j][s] is only depend upon the current and previous row values of DP. So to optimize the space complexity we use a single 2D vector to store the computations.

Implementation:

C++

#include <bits/stdc++.h>
using namespace std;
 
// Calculate the number of subsequences
// with given function value
int countValue(int n, int F, vector<int> v)
{
    // Initialize the DP table
    vector<vector<int> > dp(n + 1, vector<int>(1001, 0));
    dp[0][0] = 1;
 
    // Compute the DP table
    for (int i = 0; i < n; i++) {
        for (int k = i + 1; k >= 1; k--) {
            for (int s = 0; s <= 1000; s++) {
                int sq = v[i] * v[i];
 
                // Recurrence relation
                if (s + sq <= 1000) {
                    dp[k][s + sq] += dp[k - 1][s];
                }
            }
        }
    }
 
    // Compute the final count
    int cnt = 0;
    for (int k = 1; k <= n; k++) {
        cnt += dp[k][k * F];
    }
    return cnt;
}
 
// Driver Code
int main()
{
    vector<int> v = { 1, 2, 1, 2 };
    int F = 2, N = v.size();
 
    // Function call
    cout << countValue(N, F, v);
    return 0;
}

Java

import java.util.*;
 
public class GFG {
    // Calculate the number of subsequences
    // with the given function value
    public static int countValue(int n, int F, ArrayList<Integer> v) {
        // Initialize the DP table
        int[][] dp = new int[n + 1][1001];
        dp[0][0] = 1;
 
        // Compute the DP table
        for (int i = 0; i < n; i++) {
            for (int k = i + 1; k >= 1; k--) {
                for (int s = 0; s <= 1000; s++) {
                    int sq = v.get(i) * v.get(i);
 
                    // Recurrence relation
                    if (s + sq <= 1000) {
                        dp[k][s + sq] += dp[k - 1][s];
                    }
                }
            }
        }
 
        // Compute the final count
        int cnt = 0;
        for (int k = 1; k <= n; k++) {
            cnt += dp[k][k * F];
        }
        return cnt;
    }
 
    // Driver Code
    public static void main(String[] args) {
        ArrayList<Integer> v = new ArrayList<>(Arrays.asList(1, 2, 1, 2));
        int F = 2;
        int N = v.size();
 
        // Function call
        System.out.println(countValue(N, F, v));
    }
}

Python

# Calculate the number of subsequences
# with given function value
 
 
def countValue(n, F, v):
 
    # Initialize the DP table
    dp = [[0] * 1001 for _ in range(n + 1)]
    dp[0][0] = 1
 
    # Compute the DP table
    for i in range(n):
        for k in range(i + 1, 0, -1):
            for s in range(1001):
                sq = v[i] * v[i]
 
                # Recurrence relation
                if s + sq <= 1000:
                    dp[k][s + sq] += dp[k - 1][s]
 
    # Compute the final count
    cnt = 0
    for k in range(1, n + 1):
        cnt += dp[k][k * F]
 
    return cnt
 
# Driver Code
 
 
def main():
    v = [1, 2, 1, 2]
    F = 2
    N = len(v)
 
    # Function call
    result = countValue(N, F, v)
    print(result)
 
 
if __name__ == "__main__":
    main()

C#

using System;
using System.Collections.Generic;
 
public class GFG
{
    // Calculate the number of subsequences with a given 
  // function value
    public static int CountValue(int n, int F, List<int> v)
    {
        // Initialize the DP table
        int[,] dp = new int[n + 1, 1001];
        dp[0, 0] = 1;
 
        // Compute the DP table
        for (int i = 0; i < n; i++)
        {
            for (int k = i + 1; k >= 1; k--)
            {
                for (int s = 0; s <= 1000; s++)
                {
                    int sq = v[i] * v[i];
 
                    // Recurrence relation
                    if (s + sq <= 1000)
                    {
                        dp[k, s + sq] += dp[k - 1, s];
                    }
                }
            }
        }
 
        // Compute the final count
        int cnt = 0;
        for (int k = 1; k <= n; k++)
        {
            cnt += dp[k, k * F];
        }
        return cnt;
    }
 
    public static void Main(string[] args)
    {
        List<int> v = new List<int> { 1, 2, 1, 2 };
        int F = 2;
        int N = v.Count;
 
        // Function call
        int result = CountValue(N, F, v);
        Console.WriteLine(result);
    }
}

Javascript

function countValue(n, F, v) {
    const dp = new Array(n + 1).fill(null).map(() => new Array(1001).fill(0));
    dp[0][0] = 1;
    // Compute the DP table
    for (let i = 0; i < n; i++) {
        for (let k = i + 1; k >= 1; k--) {
            for (let s = 0; s <= 1000; s++) {
                const sq = v[i] * v[i];
                // Recurrence relation
                if (s + sq <= 1000) {
                    dp[k][s + sq] += dp[k - 1][s];
                }
            }
        }
    }
    // Compute the final count
    let cnt = 0;
    for (let k = 1; k <= n; k++) {
        cnt += dp[k][k * F];
    }
    return cnt;
}
// Driver Code
    const v = [1, 2, 1, 2];
    const F = 2;
    const N = v.length;
    // Function call
    console.log(countValue(N, F, v));

Output

Time Complexity: O(F*N^2)
Auxiliary Space: O(N^2)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!

Number of subsequences of an array with given function value

C++

Java

Python3

C#

Javascript

C++

Java

Python

C#

Javascript

Working with Titles and Heading – Python docx Module

Creating a Receipt Calculator using Python

One Liner for Python if-elif-else Statements

LEAVE A REPLY Cancel reply

Most Popular

Android 16 QPR2 Beta 3 lands with a flurry of bug fixes

Google is working on dedicated ‘Bills’ and ‘Travel’ folders for Gmail

Mint Mobile’s big bet on 5G home internet might change everything

Interviewed With Kyle Smith – Founder and CEO of Escalated by Shauli Zacks

EDITOR PICKS

Android 16 QPR2 Beta 3 lands with a flurry of bug fixes

Google is working on dedicated ‘Bills’ and ‘Travel’ folders for Gmail

Mint Mobile’s big bet on 5G home internet might change everything

POPULAR POSTS

Android 16 QPR2 Beta 3 lands with a flurry of bug fixes

Google is working on dedicated ‘Bills’ and ‘Travel’ folders for Gmail

Mint Mobile’s big bet on 5G home internet might change everything

POPULAR CATEGORY

ABOUT US

FOLLOW US