Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
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.
Frequently Asked Questions
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

Author 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.

Let S Get Started GIFs | Tenor

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
Illustration

 

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)
	{
		
		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 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!

Previous article
Path exists in the matrix with the addition of element is at most K.
Next article
Fast Fourier Transform for polynomial multiplication
Live masterclass