Nson Nson - 1 month ago 9
C++ Question

How to effectively make ascending sequences?

I am currently trying to make a program which involves ascending sequences. N is for the size of the sequence and K is the maximum number, for example

Input:

2,3


Output:
6 (1,1 - 1,2 - 1,3 - 2,2 - 2,3 - 3,3)


My current code doesn't output 6 but 3. I know this is probably not the way to find the amount of sequences. From what I see, something is wrong in the recursion. Can you please help me find the problem and fix it?

#include<iostream>
using namespace std;
long long n,k,cnt=0;
long long seq(long long n, long long k, long long first){
if(n==first){
return cnt;
}
for(long long i=first;i<=k;i++){
cnt = cnt + 1;
}
return seq(n,k,first+1);
}
int main()
{
long long n,k;
cin>>n>>k;
cout<<seq(n,k,1);
return 0;
}

Answer

This function should do it for a given n and k

long long seq(long long n, long long k,long long first,long long depth){
   if(depth > n){
       cnt = cnt + 1; // A leaf node is hit in the recursion tree
       return cnt;
   }
   else {
       for(long long i= first;i<=k;i++){    
            seq(n,k,i,depth+1); // Continue recursion
       }
   }
   return cnt;
}
int main()
{
    long long n,k;
    cin>>n>>k;
    cout<<seq(n,k,1,1);
    return 0;
}

Running code here : http://cpp.sh/4xr7a