Find all valid combinations of at most K numbers that sum up to N
Given two numbers N and K, the task is to find all valid combinations of at most K numbers that sum up to N such that the following conditions are true:
- Only numbers 1 through 9 are used.
- Each number is used at most once.
Return a list of all possible valid combinations
Examples:
Input: K = 3, N = 7
Output:
1 2 4
1 6
2 5
3 4
7Input: K = 3, N = 9
Output:
1 2 6
1 3 5
1 8
2 3 4
2 7
3 6
4 5
9
Naive Approach: The idea is to create an array of numbers from 1 to 9, and find all subsequences of length at most K with sum N.
Time Complexity: O(10^2)
Auxiliary Space: O(10^2)
Recursive Approach: The problem can also be solved using Recursion as follows:
- Create an array of digits 1-9 in arr.
- Create a recursive function that iterates the array with current index as i, current sum as sum, current count as c, current selection as temp, and current resultant vector as ans.
- Base case 1: if (sum == n && c <= k)
- Insert temp vector into ans vector
- Return the ans vector
- Base case 2: if (i >= arr.size() || sum > n || c > k)
- Return the ans vector as the current constraints have been violated
- Else
- Push current array element into temp vector
- Call the recursive function
- Pop the current element from the vector
- Call the recursive function
Below is the implementation of the above approach:
C++
// C++ code to solve the above problem #include <algorithm> #include <cmath> #include <cstdio> #include <iostream> #include <vector> using namespace std; // Recursive program to find // all combinations of at most K // digits with sum N vector<vector< int > > rec(vector< int >& arr, int i, int k, int c, int n, vector<vector< int > >& ans, vector< int >& temp, int sum) { // Base case 1 if (sum == n && c <= k) { ans.push_back(temp); return ans; } // Base case 2 if (i >= arr.size() || sum > n || c > k) return ans; // Insert arr[i] into current selection // and call recursive function temp.push_back(arr[i]); ans = rec(arr, i + 1, k, c + 1, n, ans, temp, sum + arr[i]); // Remove arr[i] from current selection // and call recursive function temp.pop_back(); ans = rec(arr, i + 1, k, c, n, ans, temp, sum); return ans; } // Function to solve the problem // and print the list of combinations void combinationSum( int k, int n) { vector< int > arr(9, 0); for ( int i = 1; i <= 9; i++) arr[i - 1] = i; vector<vector< int > > ans; vector< int > temp; // Recursive function call ans = rec(arr, 0, k, 0, n, ans, temp, 0); // Print the output[][] array for ( int i = 0; i < ans.size(); i++) { for ( auto x : ans[i]) cout << x << " " ; cout << endl; } } // Driver Code int main() { int N = 7, K = 3; combinationSum(K, N); return 0; } |
Java
// Java program for above approach import java.io.*; import java.util.*; import java.util.ArrayList; class GFG { // Recursive program to find // all combinations of at most K // digits with sum N static ArrayList<ArrayList<Integer> > rec( int [] arr, int i, int k, int c, int n, ArrayList<ArrayList<Integer> > ans, ArrayList<Integer> temp, int sum) { // Base case 1 if (sum == n && c <= k) { ans.add( new ArrayList<Integer>(temp)); return ans; } // Base case 2 if (i >= arr.length || sum > n || c > k) return ans; // Insert arr[i] into current selection // and call recursive function temp.add(arr[i]); ans = rec(arr, i + 1 , k, c + 1 , n, ans, temp, sum + arr[i]); // Remove arr[i] from current selection // and call recursive function int index = temp.size() - 1 ; temp.remove(index); ans = rec(arr, i + 1 , k, c, n, ans, temp, sum); return ans; } // Function to solve the problem // and print the list of combinations static void combinationSum( int k, int n) { int [] arr = new int [ 9 ]; for ( int i = 0 ; i < 9 ; i++) { arr[i] = 0 ; } for ( int i = 1 ; i <= 9 ; i++) arr[i - 1 ] = i; ArrayList<ArrayList<Integer> > ans = new ArrayList<ArrayList<Integer> >(); ArrayList<Integer> temp = new ArrayList<Integer>(); // Recursive function call ans = rec(arr, 0 , k, 0 , n, ans, temp, 0 ); // Print the output[][] array for (List<Integer> list : ans){ for (Integer item : list) System.out.print(item+ " " ); System.out.print( "\n" ); } } // driver code public static void main(String[] args) { int N = 7 , K = 3 ; combinationSum(K, N); } } // This code is contributed by Pushpesh Raj |
Python3
# python3 code to solve the above problem # Recursive program to find # all combinations of at most K # digits with sum N def rec(arr, i, k, c, n, ans, temp, sum ): # Base case 1 if ( sum = = n and c < = k): ans.append(temp.copy()) return ans # Base case 2 if (i > = len (arr) or sum > n or c > k): return ans # Insert arr[i] into current selection # //and call recursive function temp.append(arr[i]) ans = rec(arr, i + 1 , k, c + 1 , n, ans, temp, sum + arr[i]) # Remove arr[i] from current selection # and call recursive function temp.pop() ans = rec(arr, i + 1 , k, c, n, ans, temp, sum ) return ans # Function to solve the problem # and print the list of combinations def combinationSum(k, n): arr = [ 0 for _ in range ( 9 )] for i in range ( 1 , 10 ): arr[i - 1 ] = i ans = [] temp = [] # Recursive function call ans = rec(arr, 0 , k, 0 , n, ans, temp, 0 ) # Print the output[][] array for i in range ( 0 , len (ans)): for x in ans[i]: print (x, end = " " ) print () # Driver Code if __name__ = = "__main__" : N, K = 7 , 3 combinationSum(K, N) # This code is contributed by rakeshsahni |
C#
// C# program for above approach using System; using System.Collections.Generic; public class GFG { // Recursive program to find // all combinations of at most K // digits with sum N static List<List< int > > rec( int [] arr, int i, int k, int c, int n, List<List< int > > ans, List< int > temp, int sum) { // Base case 1 if (sum == n && c <= k) { ans.Add( new List< int >(temp)); return ans; } // Base case 2 if (i >= arr.Length || sum > n || c > k) return ans; // Insert arr[i] into current selection // and call recursive function temp.Add(arr[i]); ans = rec(arr, i + 1, k, c + 1, n, ans, temp, sum + arr[i]); // Remove arr[i] from current selection // and call recursive function int index = temp.Count - 1; temp.RemoveAt(index); ans = rec(arr, i + 1, k, c, n, ans, temp, sum); return ans; } // Function to solve the problem // and print the list of combinations static void combinationSum( int k, int n) { int [] arr = new int [9]; for ( int i = 0; i < 9; i++) { arr[i] = 0; } for ( int i = 1; i <= 9; i++) arr[i - 1] = i; List<List< int > > ans = new List<List< int > >(); List< int > temp = new List< int >(); // Recursive function call ans = rec(arr, 0, k, 0, n, ans, temp, 0); // Print the output[,] array foreach (List< int > list in ans){ foreach ( int item in list) Console.Write(item+ " " ); Console.Write( "\n" ); } } // driver code public static void Main(String[] args) { int N = 7, K = 3; combinationSum(K, N); } } // This code contributed by shikhasingrajput |
Javascript
// JavaScript program // Function to solve the problem // and print the list of combinations function combinationSum(k, n) { let arr = Array(9).fill(0); for (let i = 0; i < 9; i++) { arr[i] = i + 1; } let ans = []; let temp = []; // Recursive program to find // all combinations of at most K // digits with sum N function rec(arr, i, k, c, n, ans, temp, sum) { if (sum === n && c <= k) { ans.push(temp.slice()); return ans; } if (i >= arr.length || sum > n || c > k) { return ans; } // Insert arr[i] into current selection // and call recursive function temp.push(arr[i]); ans = rec(arr, i + 1, k, c + 1, n, ans, temp, sum + arr[i]); // Remove arr[i] from current selection // and call recursive function temp.pop(); ans = rec(arr, i + 1, k, c, n, ans, temp, sum); return ans; } // Recursive function call ans = rec(arr, 0, k, 0, n, ans, temp, 0); // Print the output[][] array for (let i = 0; i < ans.length; i++) { console.log(ans[i].join( ' ' )); } } // Driver code let N = 7, K = 3; combinationSum(K, N); // This code is contributed by anskalyan3. |
Output
1 2 4 1 6 2 5 3 4 7
Time Complexity: O(2^k), where k is the maximum recursion depth.
Auxiliary Space: O(2^k + k).
Contact Us