# Print all possible K-length subsequences of first N natural numbers with sum N

Given two positive integers **N** and **K**, the task is to print all possible **K**-length subsequences from first **N** natural numbers whose sum of elements is equal to **N**.

**Examples:**

Input:N = 5, K = 3Output:{ {1, 1, 3}, {1, 2, 2}, {1, 3, 1}, {2, 1, 2}, {2, 2, 1}, {3, 1, 1} }Explanation:

1 + 1 + 3 = N(= 5) and length is K(= 3)

1 + 2 + 2 = N(= 5) and length is K(= 3)

1 + 3 + 1 = N(= 5) and length is K(= 3)

2 + 1 + 2 = N(= 5) and length is K(= 3)

2 + 2 + 1 = N(= 5) and length is K(= 3)

3 + 1 + 1 = N(= 5) and length is K(= 3)

Input:N = 3, K = 3Output:{ {1, 1, 1} }

**Approach:** The problem can be solved using backtracking technique. Below is the recurrence relation:

Follow the steps below to solve the problem:

- Initialize a 2D array say,
**res[][]**to store all possible subsequences of length**K**whose sum is equal to**N**. - Use the above recurrence relation and find all possible subsequences of length
**K**whose sum is equal to**N**. - Finally, print the
**res[][]**array.

Below is the implementation of the above approach:

## C++

`// C++ program to implement` `// the above approach` `#include <bits/stdc++.h>` `using` `namespace` `std;` `// Function to print all subsequences of length` `// K from N natural numbers whose sum equal to N` `void` `findSub(vector<vector<` `int` `> >& res, ` `int` `sum,` ` ` `int` `K, ` `int` `N, vector<` `int` `>& temp)` `{` ` ` `// Base case` ` ` `if` `(K == 0 && sum == 0) {` ` ` `res.push_back(temp);` ` ` `return` `;` ` ` `}` ` ` `if` `(sum <= 0 || K <= 0) {` ` ` `return` `;` ` ` `}` ` ` `// Iterate over the range [1, N]` ` ` `for` `(` `int` `i = 1; i <= N; i++) {` ` ` `// Insert i into temp` ` ` `temp.push_back(i);` ` ` `findSub(res, sum - i, K - 1, N, temp);` ` ` `// Pop i from temp` ` ` `temp.pop_back();` ` ` `}` `}` `// Utility function to print all subsequences` `// of length K with sum equal to N` `void` `UtilPrintSubsequncesOfKSumN(` `int` `N, ` `int` `K)` `{` ` ` `// Store all subsequences of length K` ` ` `// from N natural numbers` ` ` `vector<vector<` `int` `> > res;` ` ` `// Store current subsequence of` ` ` `// length K from N natural numbers` ` ` `vector<` `int` `> temp;` ` ` `findSub(res, N, K, N, temp);` ` ` `// Stores total count` ` ` `// of subsequences` ` ` `int` `sz = res.size();` ` ` `// Print all subsequences` ` ` `cout << ` `"{ "` `;` ` ` `// Treaverse all subsequences` ` ` `for` `(` `int` `i = 0; i < sz; i++) {` ` ` `cout << ` `"{ "` `;` ` ` `// Print current subsequence` ` ` `for` `(` `int` `j = 0; j < K; j++) {` ` ` `// If current element is last` ` ` `// element of subsequence` ` ` `if` `(j == K - 1)` ` ` `cout << res[i][j] << ` `" "` `;` ` ` `else` ` ` `cout << res[i][j] << ` `", "` `;` ` ` `}` ` ` `// If current subsequence is last` ` ` `// subsequence from n natural numbers` ` ` `if` `(i == sz - 1)` ` ` `cout << ` `"}"` `;` ` ` `else` ` ` `cout << ` `"}, "` `;` ` ` `}` ` ` `cout << ` `" }"` `;` `}` `// Driver Code` `int` `main()` `{` ` ` `int` `N = 4;` ` ` `int` `K = 2;` ` ` `UtilPrintSubsequncesOfKSumN(N, K);` `}` |

## Java

`// Java program to implement` `// the above approach` `import` `java.io.*;` `import` `java.util.*;` `import` `java.util.stream.Collectors;` `class` `GFG {` ` ` `// Function to print all subsequences of length` ` ` `// K from N natural numbers whose sum equal to N` ` ` `static` `void` `findSub(List<List<Integer> > res, ` `int` `sum,` ` ` `int` `K, ` `int` `N, List<Integer> temp)` ` ` `{` ` ` `// Base case` ` ` `if` `(K == ` `0` `&& sum == ` `0` `) {` ` ` `List<Integer> newList = temp.stream().collect(` ` ` `Collectors.toList());` ` ` `res.add(newList);` ` ` `return` `;` ` ` `}` ` ` `if` `(sum <= ` `0` `|| K <= ` `0` `) {` ` ` `return` `;` ` ` `}` ` ` `// Iterate over the range [1, N]` ` ` `for` `(` `int` `i = ` `1` `; i <= N; i++) {` ` ` `// Insert i into temp` ` ` `temp.add(i);` ` ` `findSub(res, sum - i, K - ` `1` `, N, temp);` ` ` `// Pop i from temp` ` ` `temp.remove(temp.size() - ` `1` `);` ` ` `}` ` ` `}` ` ` `// Utility function to print all subsequences` ` ` `// of length K with sum equal to N` ` ` `static` `void` `UtilPrintSubsequncesOfKSumN(` `int` `N, ` `int` `K)` ` ` `{` ` ` `// Store all subsequences of length K` ` ` `// from N natural numbers` ` ` `@SuppressWarnings` `(` `"unchecked"` `)` ` ` `List<List<Integer> > res = ` `new` `ArrayList();` ` ` `// Store current subsequence of` ` ` `// length K from N natural numbers` ` ` `@SuppressWarnings` `(` `"unchecked"` `)` ` ` `List<Integer> temp = ` `new` `ArrayList();` ` ` `findSub(res, N, K, N, temp);` ` ` `// Stores total count` ` ` `// of subsequences` ` ` `int` `sz = res.size();` ` ` `// Print all subsequences` ` ` `System.out.print(` `"{ "` `);` ` ` `// Treaverse all subsequences` ` ` `for` `(` `int` `i = ` `0` `; i < sz; i++) {` ` ` `System.out.print(` `"{ "` `);` ` ` `// Print current subsequence` ` ` `for` `(` `int` `j = ` `0` `; j < K; j++) {` ` ` `// If current element is last` ` ` `// element of subsequence` ` ` `if` `(j == K - ` `1` `)` ` ` `System.out.print(res.get(i).get(j)` ` ` `+ ` `" "` `);` ` ` `else` ` ` `System.out.print(res.get(i).get(j)` ` ` `+ ` `", "` `);` ` ` `}` ` ` `// If current subsequence is last` ` ` `// subsequence from n natural numbers` ` ` `if` `(i == sz - ` `1` `)` ` ` `System.out.print(` `"}"` `);` ` ` `else` ` ` `System.out.print(` `"}, "` `);` ` ` `}` ` ` `System.out.print(` `" }"` `);` ` ` `}` ` ` `// Driver code` ` ` `public` `static` `void` `main(String[] args)` ` ` `{` ` ` `int` `N = ` `4` `;` ` ` `int` `K = ` `2` `;` ` ` `UtilPrintSubsequncesOfKSumN(N, K);` ` ` `}` `}` `// This code is contributed by jithin.` |

**Output:**

{ { 1, 3 }, { 2, 2 }, { 3, 1 } }

**Time Complexity:** O(2^{N})**Auxiliary Space:** O(X), where X denotes the count of subsequences of length K whose sum is N

Attention reader! Don’t stop learning now. Get hold of all the important mathematical concepts for competitive programming with the **Essential Maths for CP Course** at a student-friendly price. To complete your preparation from learning a language to DS Algo and many more, please refer **Complete Interview Preparation Course****.**