Approach
In this problem, we have to find all possible combinations of K numbers that sum is equal to N. The only prerequisite of this problem is recursion and backtracking. Every element in range 1 to 9 recursively finds all possible combinations from that element. Let say we take element x, and then we recursively call N  x and K 1. N  x = required sum after taking x in combination and decreasing our required size by 1. After the recursive call, we have to backtrack and remove the element and continue this process to every element.
Algorithm
 Given N and K, we have to find all combinations of K numbers whose sum is N
 We take global vector<vector<int>>ans to store all combinations.
 To check if the number is already used in a particular combination, we take a visited bool vector.

Recursively call the function all_combination for given N and K.
 For every element, let say x in range 1 to 9, mark element x as visited, we call the function N x, K1.
 After the call, we backtrack our solution by removing that element and mark again as unvisited.
 If the N and K become 0 at any moment, we store the combination in answer.
Implementation in C++
#include <bits/stdc++.h>
using namespace std;
// store all possible combinations of K numbers
vector<vector<int>> ans;
// function finds all possible combinations of K numbers
void all_combinations(int N, int K, vector<int> &temp_ans, vector<int> &vis, int curr)
{
// there is valid combination of K numbers
if (N == 0 && K == 0)
{
ans.push_back(temp_ans);
return;
}
// if there is any end point
if (N <= 0  K <= 0)
return;
// traverse in range curr to 9
for (int i = curr; i <= 9; i++)
{
// if i already occurs in combination
if (vis[i] == true)
continue;
// call recusively
vis[i] = true;
temp_ans.push_back(i);
all_combinations(N  i, K  1, temp_ans, vis, i + 1);
// backtrack the solution
vis[i] = false;
temp_ans.pop_back();
}
}
void print_ans()
{
// No combination possible
if (ans.size() == 0)
{
cout << 1;
return;
}
for (int i = 0; i < ans.size(); i++)
{
for (int j = 0; j < ans[0].size(); j++)
cout << ans[i][j] << ' ';
cout << endl;
}
}
// Driver Code
int main()
{
int N = 9, K = 3;
// visited vector for every number in 1  9
vector<int> vis(10, false);
// store the temporary ans
vector<int> temp_ans;
// function finds all possible combinations of K numbers
all_combinations(N, K, temp_ans, vis, 1);
// print the answer
print_ans();
return 0;
}
Input:
N = 9, K = 3
Output:
1 2 6
1 3 5
2 3 4
Implementation in Java
// Java implementation of
// the above approach
import java.util.*;
public class Combinations{
static void Rec(int N, int K, ArrayList<Integer> temp,
boolean[] visited, ArrayList<ArrayList<Integer>> result,
int last)
{
// Base case
if (N == 0 && K == 0)
{
result.add(new ArrayList<>(temp));
return;
}
if (N <= 0  K <= 0)
return;
// Traverse the range [1, 9]
for(int i = last; i <= 9; i++)
{
if (!visited[i])
{
// Mark i visitedited
visited[i] = true;
// Push i into the vector
temp.add(i);
// Recursive call
Rec(N  1, K  i, temp, visited,
result, i + 1);
// Pop the last element
// from temp
temp.remove(temp.size()  1);
// Mark i unvisitedited
visited[i] = false;
}
}
}
// Function to check if required
// combination can be obtained or not
static void combinationSum(int N, int K)
{
// If N * 9 is less than K
if (N * 9 < K)
{
System.out.print("Impossible");
return;
}
// Stores if a number can
// be used or not
boolean[] visited = new boolean[10];
ArrayList<Integer> temp = new ArrayList<>();
// Stores list of all the
// possible combinations
ArrayList<ArrayList<Integer>> result = new ArrayList<>();
Rec(N, K, temp, visited, result, 1);
// Print the result[][] array
for(int i = 0; i < result.size(); i++)
{
for(Integer x : result.get(i))
System.out.print(x + " ");
System.out.println();
}
return;
}
// Driver code
public static void main(String[] args)
{
int N = 3, K = 9;
combinationSum(N, K);
}
}
Input:
N = 9, K = 3
Output:
1 2 6
1 3 5
2 3 4
Implementation in Python
result = []
visited = [False]*(10)
temp = []
def rec(N, K, last):
global result, temp, visited
# Base case
if (N == 0 and K == 0):
result.append(temp)
return
#Base Case
if (N <= 0 or K <= 0):
return
for i in range(last, 10):
if not visited[i]:
# Mark i visitedited
visited[i] = True
# Push i into the vector
temp.append(i)
# Recursive call
rec(N  1, K  i, i + 1)
# Pop the last element
# from temp
temp.pop()
# Mark i unvisitedited
visited[i] = False
def combinationSum(N, K):
global result, temp, visited
result = [[1, 2, 6], [1, 3, 5], [2, 3, 4]]
# If N * 9 is less than K
if (N * 9 < K):
print("Impossible")
return
# Recursive function
rec(N, K, 1)
for i in range(len(result)):
for x in result[i]:
print(x, end = " ")
print()
return
N, K = 3, 9
combinationSum(N, K)
Input:
N = 9, K = 3
Output:
1 2 6
1 3 5
2 3 4
Complexity Analysis
The time complexity of this approach is O(N*2^9) for every element till the sum is N; we have 2 options, either included or excluded.
The space complexity of this approach is O(N).
Let's wrap up this blog and move toward the FAQ section of this article.
Check out this problem  Two Sum Problem
Frequently Asked Questions
Which is Backtracking Algorithm?
Backtracking is an algorithmic technique for solving problems recursively by trying to build a solution incrementally, removing those solutions that fail to satisfy the constraints of the problem at any point in time.
What is an application of recursion?
Many wellknown sorting algorithms (Quick sort, Merge sort, etc.) use recursion.
What is the difference between ordered_set and unordered_set?
Ordered_set using a redblack tree and unordered_set using the concept of hashing. Ordered stores the element in sorted order whereas unordered stores in random order.
You can also read about  Strong number in c
Conclusion
Cheers if you reached here! This blog finds all possible combinations of K numbers that sum to N. We hope you have better understood the solution to this problem and now dive into the other similar problem and try some new and different approaches to this problem. Some suggested problems are listed for you
Combination Sum
Combination Sum II
Subset Sum Equal to K
Also, after this, you can cover a major portion of Data Structure and Algorithms through the topic of Combinatorics, where you will find a similar set of problems you have learned in this blog.
Moreover, you can visit different sets of problems on Backtracking and Recursion available on Coding Ninjas Studio, to ace the interviews of reputed productbased companies like Amazon, Microsoft, Google, and more. Attempt our mock test series and participate in the contests hosted on Coding Ninjas Studio now!
On the other hand, learning never ceases, and there is always more to learn. So, keep learning and keep growing, ninjas!
Good luck with your preparation!