Generate all possible combinations of K numbers that sum to N

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;
}

You can also try this code with Online C++ Compiler

Run Code

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);
}
}

You can also try this code with Online Java Compiler

Run Code

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)

You can also try this code with Online Python Compiler

Run Code

Input:

N = 9, K = 3

Output:

1 2 6 
1 3 5 
2 3 4

You can also try this code with Online Python Compiler

Run Code

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!