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 = 3
Output: { {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 = 3
Output: { {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 << "{ " ; // Traverse 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( "{ " ); // Traverse 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. |
Python3
# Python program to implement # the above approach # Function to print all subsequences of length # K from N natural numbers whose sum equal to N def findSub(res, sum ,K,N,temp): # Base case if (K = = 0 and sum = = 0 ): res.append(temp[:]) return if ( sum < = 0 or K < = 0 ): return # Iterate over the range [1, N] for i in range ( 1 ,N): # Insert i into temp temp.append(i) findSub(res, sum - i, K - 1 , N, temp) # Pop i from temp temp.pop() # Utility function to print all subsequences # of length K with sum equal to N def UtilPrintSubsequncesOfKSumN(N, K): # Store all subsequences of length K # from N natural numbers res = [] # Store current subsequence of # length K from N natural numbers temp = [] findSub(res, N, K, N, temp) # # Stores total count # # of subsequences sz = len (res) # Print all subsequences print ( "{" ,end = " " ) # Traverse all subsequences for i in range (sz): print ( "{" ,end = " " ) # Print current subsequence for j in range (K): # If current element is last # element of subsequence if (j = = K - 1 ): print (res[i][j],end = " " ) else : print (res[i][j],end = ", " ) # If current subsequence is last # subsequence from n natural numbers if (i = = sz - 1 ): print ( "}" ,end = "") else : print ( "}," ,end = " " ) print ( " }" ) # Driver Code N = 4 K = 2 UtilPrintSubsequncesOfKSumN(N, K) # This code is contributed by shinjanpatra |
C#
using System; using System.Collections.Generic; using System.Linq; namespace GFG { class Program { // Function to print all subsequences of length // K from N natural numbers whose sum equal to N static void FindSub(List<List< int > > res, int sum, int K, int N, List< int > temp) { // Base case if (K == 0 && sum == 0) { List< int > newList = temp.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.RemoveAt(temp.Count - 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 var res = new List<List< int > >(); // Store current subsequence of // length K from N natural numbers var temp = new List< int >(); FindSub(res, N, K, N, temp); // Stores total count // of subsequences int sz = res.Count; // Print all subsequences Console.Write( "{ " ); // Traverse all subsequences for ( int i = 0; i < sz; i++) { Console.Write( "{ " ); // Print current subsequence for ( int j = 0; j < K; j++) { // If current element is last // element of subsequence if (j == K - 1) Console.Write(res[i][j] + " " ); else Console.Write(res[i][j] + ", " ); } // If current subsequence is last // subsequence from n natural numbers if (i == sz - 1) Console.Write( "}" ); else Console.Write( "}, " ); } Console.WriteLine( " }" ); } static void Main( string [] args) { int N = 4; int K = 2; UtilPrintSubsequncesOfKSumN(N, K); } } } // This code is contributed by phasing17. |
Javascript
// Python program to implement // the above approach // Function to print all subsequences of length // K from N natural numbers whose sum equal to N function findSub(res,sum,K,N,temp) { // Base case if (K == 0 && sum == 0) { res.push([...temp]) return } if (sum <= 0||K <= 0) return // Iterate over the range [1, N] for ( var i = 1; i < N; i++) { // Insert i into temp temp.push(i) findSub(res, sum - i, K - 1, N, temp) // Pop i from temp temp.pop() } } // Utility function to print all subsequences // of length K with sum equal to N function UtilPrintSubsequncesOfKSumN(N, K) { // Store all subsequences of length K // from N natural numbers let res = [] // Store current subsequence of // length K from N natural numbers let temp = [] findSub(res, N, K, N, temp) // // Stores total count // // of subsequences let sz = res.length // Print all subsequences process.stdout.write( "{" + " " ) // Traverse all subsequences for ( var i = 0; i < sz; i++) { process.stdout.write( "{" + " " ) // Print current subsequence for ( var j = 0; j < K; j++) { // If current element is last // element of subsequence if (j == K - 1) process.stdout.write(res[i][j]+ " " ) else process.stdout.write(res[i][j] + ", " ) } // If current subsequence is last // subsequence from n natural numbers if (i == sz - 1) process.stdout.write( "}" + "" ) else process.stdout.write( "}," + " " ) } process.stdout.write( " }" ) } // Driver Code let N = 4 let K = 2 UtilPrintSubsequncesOfKSumN(N, K) // This code is contributed by phasing17 |
Output:
{ { 1, 3 }, { 2, 2 }, { 3, 1 } }
Time Complexity: O(2N)
Auxiliary Space: O(X), where X denotes the count of subsequences of length K whose sum is N