Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
1.
Introduction
2.
Problem Statement
2.1.
Sample Examples
3.
Approach
3.1.
Algorithm
3.2.
Implementation in C++
3.3.
Implementation in Java
3.4.
Implementation in Python
3.5.
Complexity Analysis
4.
4.1.
Which is Backtracking Algorithm?
4.2.
What is an application of recursion?
4.3.
What is the difference between ordered_set and unordered_set?
5.
Conclusion
Last Updated: Mar 27, 2024
Medium

# Generate all possible combinations of K numbers that sum to N

Ayush Tiwari
0 upvote

## Introduction

Hello Ninjas!! We are back with a new problem based on data structure, i.e. to Generate all possible combinations of K numbers that sum to N.

This blog will brief you about the problem, the approach to the problem, and its implementation in different languages. Let's discuss the problem statement.

Source: Giphy

## Problem Statement

The problem states that if you are given two integers, N and K, you have to find all possible combinations of K numbers whose sum is N with some conditions:

1. Only numbers from [1, 9] are allowed.
2. In one combination, each number appears at most once.

If there is no such combination, then print -1.

So before we go to the solution to this problem, we should first look at some examples to understand the problem better.

#### Sample Examples

Example - 1

``````Given - N=9, K=3
Output -
2 3 4
1 2 6
1 3 5``````

Explanation- all possible combinations of K numbers :

For given sum = 9 there are 3 combination possible

2 + 3 + 4 = 9 and each number appears at most once

1 + 2 + 6 = 9 and each number appears at most once

1 + 3 + 5 = 9 and each number appears at most once

Example - 2

``````Given - N = 28 , K=3
Output - -1``````

Explanation- There is no such combination of size 3 with sum = 28

Also see, Euclid GCD Algorithm

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

## 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

1. Given N and K, we have to find all combinations of K numbers whose sum is N
2. We take global vector<vector<int>>ans to store all combinations.
3. To check if the number is already used in a particular combination, we take a visited bool vector.
4. Recursively call the function all_combination for given N and K.
1. For every element, let say x in range 1 to 9, mark element x as visited, we call the function N -x, K-1.
2. After the call, we backtrack our solution by removing that element and mark again as unvisited.
5. 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)
{

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

// 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 well-known sorting algorithms (Quick sort, Merge sort, etc.) use recursion.

### What is the difference between ordered_set and unordered_set?

Ordered_set using a red-black 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 product-based 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!

Live masterclass