LeetCode Problem Distinct SubSequence, what is wrong with my code

Problem Link : Distinct Subsequence

solution :Solution Link

using namespace std;
#define ll long long int
#define ull unsigned long long
#define endl "\n"
#define boost                         \
    ios_base::sync_with_stdio(false); \
#define Mod (int)(1e9+ 7)
#define fl(i, a,b) for(int i = a; i < b; i++)
void func(string s, string p, string temp, int idx,int &ans){
    // temp == p
    if(temp == p){
        ans += 1;
    // size of temp > size of p 
    if(temp.length() >= p.length() || idx >= s.size() ){
    func(s, p, temp + s[idx], idx+1, ans);
    func(s, p, temp, idx+1, ans);

int solve(string s, string p){
    int ans = 0;
    if(s.length() < p.length()){
        return ans;
    func(s, p, "", 0, ans);
    return ans;
int main() {
    int tc;
        string s, t;
        cout<<solve(s, t)<<endl;
    return 0;

test case : “bccbcdcabadabddbccaddcbabbaaacdba” “bccbbdc”
I got segmentation error.
I am not finding the error in this solution.
plz help finding the error

Time complexity of your code is N*(2^N) i.e. (2^1000) and the + operation is of O(N) in strings.

1 Like

thanks for your response :blush:

But why are recursion going for infinite time ?
at mention testcase

2^1000 it’s going because you are considering every subset

So, we have to use only dynamic programming ?

Can we use any other approach ?

I don’t know any other approach

1 Like

thanks for your response. :blush:

The idea behind this question is common about longest common subsequences

Just we have to count aall the LCS


First of all see that we have to found LCS

Eg:- The given two strings are

  1. rabbbit and 2. rabbit

In the explanation of this test cases you can see that all generated subsequence are LCS.

So we have to find the LCS

But there can be many such subsequence so find all the LCS

So we can’t do it ?