Print all combinations using Backtracking
The idea is to use a recursive approach to construct these combinations by starting with an empty combination and gradually building it up, considering each number in the range from 1 to n. All possible combinations are explored by recursively including or excluding each number and backtracking as needed.
Step-by-step approach:
- Start with an empty array temp that stores the current combination being constructed.
- For each element, it either includes it in the current combination or skips it, based on the value of k (The number of elements left to be included in the combination).
- If k reaches 0, it means k elements have been selected, we temp array to final result.
Below is the implementation of the above approach:
C++
// C++ program to print all combinations of size // k of elements in set 1..n #include <bits/stdc++.h> using namespace std; void makeCombiUtil(vector<vector< int > >& ans, vector< int >& tmp, int n, int left, int k) { // Pushing this vector to a vector of vector if (k == 0) { ans.push_back(tmp); return ; } // i iterates from left to n. First time // left will be 1 for ( int i = left; i <= n; ++i) { tmp.push_back(i); makeCombiUtil(ans, tmp, n, i + 1, k - 1); // Popping out last inserted element // from the vector tmp.pop_back(); } } // Prints all combinations of size k of numbers // from 1 to n. vector<vector< int > > makeCombi( int n, int k) { vector<vector< int > > ans; vector< int > tmp; makeCombiUtil(ans, tmp, n, 1, k); return ans; } // Driver code int main() { // given number int n = 5; int k = 3; vector<vector< int > > ans = makeCombi(n, k); for ( int i = 0; i < ans.size(); i++) { for ( int j = 0; j < ans[i].size(); j++) { cout << ans.at(i).at(j) << " " ; } cout << endl; } return 0; } |
Java
// Java program to print all combinations of size // k of elements in set 1..n import java.util.*; public class Main { static Vector<Vector<Integer>> ans = new Vector<Vector<Integer>>(); static Vector<Integer> tmp = new Vector<Integer>(); static void makeCombiUtil( int n, int left, int k) { // Pushing this vector to a vector of vector if (k == 0 ) { ans.add(tmp); for ( int i = 0 ; i < tmp.size(); i++) { System.out.print(tmp.get(i) + " " ); } System.out.println(); return ; } // i iterates from left to n. First time // left will be 1 for ( int i = left; i <= n; ++i) { tmp.add(i); makeCombiUtil(n, i + 1 , k - 1 ); // Popping out last inserted element // from the vector tmp.remove(tmp.size() - 1 ); } } // Prints all combinations of size k of numbers // from 1 to n. static Vector<Vector<Integer>> makeCombi( int n, int k) { makeCombiUtil(n, 1 , k); return ans; } public static void main(String[] args) { // given number int n = 5 ; int k = 3 ; ans = makeCombi(n, k); } } // This code is contributed by suresh07. |
Python3
# Python3 program to print all combinations of size # k of elements in set 1..n ans = [] tmp = [] def makeCombiUtil(n, left, k): # Pushing this vector to a vector of vector if (k = = 0 ): ans.append(tmp) for i in range ( len (tmp)): print (tmp[i], end = " " ) print () return # i iterates from left to n. First time # left will be 1 for i in range (left, n + 1 ): tmp.append(i) makeCombiUtil(n, i + 1 , k - 1 ) # Popping out last inserted element # from the vector tmp.pop() # Prints all combinations of size k of numbers # from 1 to n. def makeCombi(n, k): makeCombiUtil(n, 1 , k) return ans # given number n = 5 k = 3 ans = makeCombi(n, k) # This code is contributed by divyeshrabadiya07. |
C#
// C# program to print all combinations of size // k of elements in set 1..n using System; using System.Collections.Generic; class GFG { static List<List< int >> ans = new List<List< int >>(); static List< int > tmp = new List< int >(); static void makeCombiUtil( int n, int left, int k) { // Pushing this vector to a vector of vector if (k == 0) { ans.Add(tmp); for ( int i = 0; i < tmp.Count; i++) { Console.Write(tmp[i] + " " ); } Console.WriteLine(); return ; } // i iterates from left to n. First time // left will be 1 for ( int i = left; i <= n; ++i) { tmp.Add(i); makeCombiUtil(n, i + 1, k - 1); // Popping out last inserted element // from the vector tmp.RemoveAt(tmp.Count - 1); } } // Prints all combinations of size k of numbers // from 1 to n. static List<List< int >> makeCombi( int n, int k) { makeCombiUtil(n, 1, k); return ans; } static void Main() { // given number int n = 5; int k = 3; ans = makeCombi(n, k); } } // This code is contributed by rameshtravel07. |
Javascript
<script> // Javascript program to print all combinations of size // k of elements in set 1..n let ans = []; let tmp = []; function makeCombiUtil(n, left, k) { // Pushing this vector to a vector of vector if (k == 0) { ans.push(tmp); for (let i = 0; i < tmp.length; i++) { document.write(tmp[i] + " " ); } document.write( "</br>" ); return ; } // i iterates from left to n. First time // left will be 1 for (let i = left; i <= n; ++i) { tmp.push(i); makeCombiUtil(n, i + 1, k - 1); // Popping out last inserted element // from the vector tmp.pop(); } } // Prints all combinations of size k of numbers // from 1 to n. function makeCombi(n, k) { makeCombiUtil(n, 1, k); return ans; } // given number let n = 5; let k = 3; ans = makeCombi(n, k); // This code is contributed by divyesh072019. </script> |
1 2 3 1 2 4 1 2 5 1 3 4 1 3 5 1 4 5 2 3 4 2 3 5 2 4 5 3 4 5
Time Complexity: O((nCk)*k), where nCk is all possible subsets and k to copy subsets into ans vector.
Auxiliary Space: O((nCk)*k), to store all n C k subset in the ans vector of size k.
Related Article:
Print all combinations | Set-1
Given two numbers n and k, you have to print all possible combinations of k numbers from 1…n.
Examples:
Input : n = 4
k = 2
Output: 1 2
1 3
1 4
2 3
2 4
3 4Input : n = 5
k = 3
Output : 1 2 3
1 2 4
1 2 5
1 3 4
1 3 5
1 4 5
2 3 4
2 3 5
2 4 5
3 4 5