Introduction
Problem statement
We are given a number N and K. Our task is to count the combinations of K numbers from 1 to N having a sum equal to N. Duplicates are allowed.
Sample Examples
Example 1:
Input: N = 5, K = 2
Output: 4
Explanation:
Combinations are: (1, 4), (4, 1), (2, 3), (3, 2)
Example 2:
Input: N = 3, K = 3
Output: 1
Explanation:
There can be only one combination = (1, 1, 1)
Naive approach
The idea is simple, run a loop from 1 to N and for every number, recursively count the number of combinations after including that number in one of the K numbers.
Finally, add all of these combinations to get the answer.
Steps of algorithm

Create a possible_comb() function which will accept 4 parameters that are N, K, sum and memo. Here N is the required sum, K is the number of elements used, the sum is the sum of numbers till now, and the memo is the matrix to memoise the result. Initially sum = 0, and the memo matrix of size (N+1) * (K+1) is filled with 1.

Check for the base cases:
 If the sum = N and K = 0, then return 1.

If the sum >= N and K >= 0, then return 0.

Run a loop from 1 to N and count the combinations after including the current number in one of the K numbers.

Add all the combinations and store them in the count variable.
 Finally, store the count in the memo matrix and return the value of count, which is the count of the combination of K numbers that sum up to N.
Implementation in C++
#include <bits/stdc++.h>
using namespace std;
int possible_comb(int N, int K, int sum, vector<vector<int> >& memo)
{
// Base Cases
if (sum == N and K == 0)
return 1;
if (sum >= N and K >= 0)
return 0;
if (K < 0)
return 0;
// If the answer is already present in memo
if (memo[sum][K] != 1) {
return memo[sum][K];
}
int count = 0;
for (int i = 1; i <= N; i++) {
count = count + possible_comb(N, K  1, sum + i, memo);
}
memo[sum][K] = count;
return memo[sum][K];
}
int main()
{
int N = 5, K = 2;
// memo matrix
vector<vector<int> > memo(N + 1, vector<int>(K + 1, 1));
cout << possible_comb(N, K, 0, memo);
}
Output:
4
Complexity Analysis
Time complexity: O(N*K), as we are using a loop from 1 to N and inside the loop, we are counting combinations of the K numbers.
Space complexity: O(N*K), as we are using a memo matrix of size (N+1) * (K+1)