In this HackerRank Wet Shark and Two Subsequences problem solution we have given an array X and we need to find all pairs of subsequences (A, B) and we need to determine how many possible subsequences A and B can exist.

## Problem solution in Python.

```#!/bin/python3

import math
import os
import random
import re
import sys

#
# Complete the 'twoSubsequences' function below.
#
# The function is expected to return an INTEGER.
# The function accepts following parameters:
#  1. INTEGER_ARRAY x
#  2. INTEGER r
#  3. INTEGER s
#
mod = 10**9+7
def twoSubsequences(x, r, s):
if r<s or (r+s)%2==1 or r==0:
return 0
h,l = (r+s)//2, (r-s)//2
m = len(x)
dp = [[0 for i in range(m+1)] for j in range(h+1)]
dp[0][0] = 1
if x[0]<=h:
dp[x[0]][1] = 1
for i in range(1, m):
for j in range(h,0,-1):
for k in range(1,m+1):
if j>=x[i]:
dp[j][k] = (dp[j][k]+dp[j-x[i]][k-1]) % mod
res = 0
for k in range(1,m+1):
res  = (res+dp[h][k]*dp[l][k]) % mod
return res

if __name__ == '__main__':
fptr = open(os.environ['OUTPUT_PATH'], 'w')

first_multiple_input = input().rstrip().split()

m = int(first_multiple_input[0])

r = int(first_multiple_input[1])

s = int(first_multiple_input[2])

x = list(map(int, input().rstrip().split()))

result = twoSubsequences(x, r, s)

fptr.write(str(result) + '\n')

fptr.close()
```

{"mode":"full","isActive":false}

## Problem solution in Java.

```import java.io.*;
import java.math.*;
import java.text.*;
import java.util.*;
import java.util.regex.*;

public class Solution {

/*
* Complete the twoSubsequences function below.
*/
static int twoSubsequences(int[] X, int r, int s) {
/*
*/
final long MOD=1000000007;
int n = (r + s) / 2, l = (r - s) / 2,m=X.length;
long result=0;
long[][] dp=new long[n + 1][m + 1];
dp[0][0] = 1;
if(X[0] <= n) {
dp[X[0]][1] = 1;
}
for(int i = 1; i < m; i++) {
dp[0][0] = 1;
for(int k = 1; k <= m; k++) {
dp[0][k] = 0;
}
for(int j = n; j >= 1; j--) {
dp[j][0] = 0;
for(int k = 1; k <= m; k++) {
if(j < X[i]) {
dp[j][k] = dp[j][k];
} else {
dp[j][k] = (dp[j - X[i]][k - 1] + dp[j][k]) % MOD;
}
}
}
}
if(l >= 0 && (r + s) % 2 != 1 && (r - s) % 2 != 1 && r != 0) {
for(int i = 0; i <= m; i++) {
result = (result + dp[n][i] * dp[l][i]) % MOD;
}
}
return (int)result;
}

private static final Scanner scanner = new Scanner(System.in);

public static void main(String[] args) throws IOException {
BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

String[] mrs = scanner.nextLine().split(" ");

int m = Integer.parseInt(mrs[0].trim());

int r = Integer.parseInt(mrs[1].trim());

int s = Integer.parseInt(mrs[2].trim());

int[] x = new int[m];

String[] xItems = scanner.nextLine().split(" ");

for (int xItr = 0; xItr < m; xItr++) {
int xItem = Integer.parseInt(xItems[xItr].trim());
x[xItr] = xItem;
}

int result = twoSubsequences(x, r, s);

bufferedWriter.write(String.valueOf(result));
bufferedWriter.newLine();

bufferedWriter.close();
}
}
```

{"mode":"full","isActive":false}

## Problem solution in C++.

```#include <bits/stdc++.h>

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define FORD(i, a, b) for(int i = (a); i >= (b); --i)
#define VAR(v, i) __typeof(i) v=(i)
#define FORE(i, c) for(VAR(i, (c).begin()); i != (c).end(); ++i)
#define all(v) (v).begin(),(v).end()

#define VI vector<int>
#define PII pair<int,int>
#define st first
#define nd second
#define mp make_pair
#define pb push_back
#define lint long long int

#define debug(x) {cerr <<#x <<" = " <<x <<endl; }
#define debug2(x,y) {cerr <<#x <<" = " <<x << ", "<<#y<<" = "<< y <<endl; }
#define debug3(x,y,z) {cerr <<#x <<" = " <<x << ", "<<#y<<" = "<< y << ", " << #z << " = " << z <<endl; }
#define debugv(x) {{cerr <<#x <<" = "; FORE(itt, (x)) cerr <<*itt <<", "; cerr <<endl; }}
#define debugt(t,n) {{cerr <<#t <<" = "; FOR(it,0,(n)) cerr <<t[it] <<", "; cerr <<endl; }}

#define make( x) int (x); scanf("%d",&(x));
#define make2( x, y) int (x), (y); scanf("%d%d",&(x),&(y));
#define make3(x, y, z) int (x), (y), (z); scanf("%d%d%d",&(x),&(y),&(z));
#define make4(x, y, z, t) int (x), (y), (z), (t); scanf("%d%d%d%d",&(x),&(y),&(z),&(t));
#define makev(v,n) VI (v); FOR(i,0,(n)) { make(a); (v).pb(a);}
#define IOS ios_base::sync_with_stdio(0)
#define HEAP priority_queue

#define read4(x, y, z, t) scanf("%d%d%d%d",&(x),&(y),&(z),&(t));
#define readv(v,n) FOR(i,0,(n)) { make(a); (v).pb(a);}

using namespace std;
#define max_n 100005

int mod = 1e9+7;
int dp[2005][105];
int dp2[2005][105];

int main(){
make3(m,r,s);
if((r+s)%2!=0){
makev(v,m);
printf("0\n");
}
else{
makev(v,m);
int sum = (r+s)/2, diff = (r-s)/2;
if(diff < 0){
printf("0\n");
return 0;
}
FOR(i,0,sum+1) FOR(j,0,m+1) dp[i][j] = 0;
dp[0][0] = 1;

FOR(i,0,m){
FOR(j,0,sum+1){
FOR(k,0,m+1){
dp2[j][k] = dp[j][k] + ((j>=v[i] && k > 0) ? dp[j-v[i]][k-1] : 0);
dp2[j][k] %= mod;
}
}
FOR(q,0,sum+1) FOR(j,0,m+1)  dp[q][j] = dp2[q][j];
}
int ans = 0;
FOR(i,1,m+1){
ans += (dp[sum][i]*1LL*dp[diff][i])%mod;
ans %= mod;
}
printf("%d\n",ans);
}
}

```

{"mode":"full","isActive":false}

## Problem solution in C.

```#include "stdio.h"
#include "string.h"

int dp[4010][102];
int a[102];
const int MOD = (1e9) + 7;

int main() {
int m, r, s;
while (scanf("%d%d%d",&m,&r,&s) != EOF) {
for (int i = 0 ; i < m ; ++i)
scanf("%d", &a[i]);
if (r == 0 && s == 0) {
printf("0\n");
continue;
}
if ((r + s) % 2 == 1 || r < s) {
printf("0\n");
continue;
}

int maxS = (r + s + 1) / 2;
memset(dp, 0, sizeof(dp));
dp[0][0] = 1;
for (int i = 0 ; i < m ; ++i) {
for (int sum = maxS ; sum >= 0 ; --sum) {
if (sum + a[i] > maxS) continue;
for (int cnt = 0 ; cnt <= i ; ++cnt) {
dp[sum+a[i]][cnt+1] += dp[sum][cnt];
dp[sum+a[i]][cnt+1] %= MOD;
}
}
}
int total = 0;
for (int cnt = 0 ; cnt <= m ; ++cnt) {
total += (int)((long long)dp[(r+s)/2][cnt] * dp[(r-s)/2][cnt] % MOD);
total %= MOD;
}
printf("%d\n",total);
}
return 0;
}
```

{"mode":"full","isActive":false}