Combinations
MedPrompt
Given two integers n and k, return all possible combinations of k numbers chosen from the range [1, n].
You may return the answer in any order.
Example 1:
Input: n = 4, k = 2
Output: [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]
Explanation: There are 4 choose 2 = 6 total combinations.
Note that combinations are unordered, i.e., [1,2] and [2,1] are considered to be the same combination.Example 2:
Input: n = 1, k = 1
Output: [[1]]
Explanation: There is 1 choose 1 = 1 total combination.
Constraints:
1 <= n <= 201 <= k <= n
Approaches
2 approaches with complexity analysis and trade-offs.
A straightforward but inefficient method is to generate all possible subsets of numbers from the range [1, n] and then select only those subsets that have a size of k. The total number of subsets for a set of n elements is 2^n. We can represent each subset using a bitmask of length n, where the i-th bit being set indicates the presence of the number i+1 in the subset.
Algorithm
- Initialize an empty list
resultto store the final combinations. - The total number of subsets of
nelements is2^n. We can iterate through all numbers from0to2^n - 1. - Each number
iin this range can be treated as a bitmask of lengthn. - For each bitmask
i:- Create a new empty list
currentCombination. - Iterate from
j = 0ton-1. - If the
j-th bit ofiis1(checked using(i >> j) & 1), it signifies that the numberj+1is part of the subset. Addj+1tocurrentCombination.
- Create a new empty list
- After constructing the subset, check if
currentCombination.size()is equal tok. - If it is, add
currentCombinationto theresultlist. - After checking all
2^nbitmasks, return theresultlist.
Walkthrough
The algorithm iterates through all numbers from 0 to 2^n - 1. Each number i serves as a bitmask. For each bitmask i, we construct a corresponding subset. We iterate from j = 0 to n-1. If the j-th bit of i is set, it means the number j+1 is included in the current subset. After constructing a subset, we check if its size is equal to k. If the size is k, we add this subset to our final list of results. This process continues until all 2^n possible subsets have been checked.
class Solution { public List<List<Integer>> combine(int n, int k) { List<List<Integer>> result = new ArrayList<>(); // Iterate through all possible subsets represented by bitmasks for (int i = 0; i < (1 << n); i++) { List<Integer> currentCombination = new ArrayList<>(); // Check which numbers are in the current subset for (int j = 0; j < n; j++) { if (((i >> j) & 1) == 1) { currentCombination.add(j + 1); } } // If the subset has size k, add it to the result if (currentCombination.size() == k) { result.add(currentCombination); } } return result; }}Complexity
Time
O(n * 2^n)
Space
O(k)
Trade-offs
Pros
Conceptually simple if you are familiar with bit manipulation for generating subsets.
It's an iterative approach that avoids recursion.
Cons
Highly inefficient due to its exponential time complexity
O(n * 2^n).Generates a large number of unnecessary subsets of sizes other than
k, leading to wasted computation.
This is the standard and most efficient approach for solving this problem. It builds the combinations one element at a time using recursion. The "backtracking" part involves undoing a choice to explore other possibilities, which prunes the search space significantly compared to the brute-force method by only building combinations of the desired length.
Algorithm
- Initialize an empty list
resultto store the final combinations. - Define a recursive helper function,
backtrack(start, currentCombination). - Base Case: If the size of
currentCombinationequalsk, a valid combination has been found. Add a copy ofcurrentCombinationtoresultand return. - Recursive Step: Iterate with a loop from
i = startton.- Choose: Add the current number
itocurrentCombination. - Explore: Make a recursive call
backtrack(i + 1, currentCombination). Passingi + 1ensures that for the next level, we only pick numbers greater thani, which prevents duplicate elements and duplicate combinations (e.g., we generate[1, 2]but not[2, 1]). - Unchoose (Backtrack): Remove the number
ifromcurrentCombination. This step is crucial as it allows the algorithm to explore other branches of the search tree, for example, moving from the path[1, 2]to[1, 3].
- Choose: Add the current number
- Start the process by calling
backtrack(1, new ArrayList<>()).
Walkthrough
We define a recursive helper function, say backtrack(start, currentCombination). The start parameter indicates the starting number for the next element to be added, ensuring we only consider numbers greater than the previous one. This avoids duplicate combinations (e.g., [1, 2] and [2, 1]) and keeps them sorted. The currentCombination list stores the combination being built. The base case for the recursion is when currentCombination.size() equals k. At this point, we have found a valid combination, so we add a copy of it to our result list and return. In the recursive step, we loop from start to n. In each iteration i, we first add i to the current combination, then make a recursive call for the next elements starting from i + 1, and finally, we remove i to backtrack and explore other possibilities.
class Solution { public List<List<Integer>> combine(int n, int k) { List<List<Integer>> result = new ArrayList<>(); backtrack(1, new ArrayList<>(), n, k, result); return result; } private void backtrack(int start, List<Integer> currentCombination, int n, int k, List<List<Integer>> result) { // Base case: a combination of size k is found if (currentCombination.size() == k) { result.add(new ArrayList<>(currentCombination)); return; } // Explore numbers from 'start' to 'n' // Optimization: we can stop if remaining numbers are not enough to form a combination for (int i = start; i <= n && n - i + 1 >= k - currentCombination.size(); i++) { // Add the number to the current combination currentCombination.add(i); // Recurse to find the next element backtrack(i + 1, currentCombination, n, k, result); // Backtrack: remove the number to explore other possibilities currentCombination.remove(currentCombination.size() - 1); } }}Complexity
Time
O(k * C(n, k))
Space
O(k)
Trade-offs
Pros
Highly efficient compared to brute force, as it doesn't explore unnecessary paths.
It is the standard, idiomatic, and elegant solution for many combinatorial problems.
Easy to understand and implement.
Cons
The recursive nature can lead to stack overflow for very deep recursion, although this is not a concern with the given constraints (
k <= 20).
Solutions
Solution
public class Solution { private List < IList < int >> ans = new List < IList < int >> (); private List < int > t = new List < int > (); private int n; private int k; public IList < IList < int >> Combine(int n, int k) { this.n = n; this.k = k; dfs(1); return ans; } private void dfs(int i) { if (t.Count == k) { ans.Add(new List < int > (t)); return; } if (i > n) { return; } for (int j = i; j <= n; ++j) { t.Add(j); dfs(j + 1); t.RemoveAt(t.Count - 1); } }}public class Combinations { public class Solution_dfs { List < List < Integer >> result = new ArrayList <>(); List < Integer > tmp = new ArrayList <>(); public List < List < Integer >> combine ( int n , int k ) { if ( k > n || n <= 0 || k <= 0 ) { return result ; } dfs ( n , k , 1 ); return result ; } private void dfs ( int n , int k , int start ) { if ( k == 0 ) { result . add ( new ArrayList <>( tmp )); return ; } for ( int i = start ; i <= n ; i ++) { tmp . add ( i ); dfs ( n , k - 1 , i + 1 ); tmp . remove ( tmp . size () - 1 ); } } } public class Solution_iteration { public List < List < Integer >> combine ( int n , int k ) { List < List < Integer >> res = new ArrayList <>(); int [] out = new int [ k ]; int i = 0 ; while ( i >= 0 ) { ++ out [ i ]; if ( out [ i ] > n ) -- i ; else if ( i == k - 1 ) res . add ( Arrays . stream ( out ). boxed (). collect ( Collectors . toList ())); else { ++ i ; out [ i ] = out [ i - 1 ]; } } return res ; } } } ////// class Solution { public List < List < Integer >> combine ( int n , int k ) { List < List < Integer >> res = new ArrayList <>(); dfs ( 1 , n , k , new ArrayList <>(), res ); return res ; } private void dfs ( int i , int n , int k , List < Integer > t , List < List < Integer >> res ) { if ( t . size () == k ) { res . add ( new ArrayList <>( t )); return ; } for ( int j = i ; j <= n ; ++ j ) { t . add ( j ); dfs ( j + 1 , n , k , t , res ); t . remove ( t . size () - 1 ); } } }class Solution {public: vector<vector<int>> combine(int n, int k) { vector<vector<int>> ans; vector<int> t; function<void(int)> dfs = [&](int i) { if (t.size() == k) { ans.emplace_back(t); return; } if (i > n) { return; } t.emplace_back(i); dfs(i + 1); t.pop_back(); dfs(i + 1); }; dfs(1); return ans; }};class Solution : def combine ( self , n : int , k : int ) -> List [ List [ int ]]: res = [] def dfs ( i , t ): # no need to check len(t)>k, when '==k' returned already if len ( t ) == k : res . append ( t . copy ()) return for j in range ( i , n + 1 ): t . append ( j ) dfs ( j + 1 , t ) t . pop () dfs ( 1 , []) # 1 to n return res class Solution_iteration : def combine ( self , n : int , k : int ) -> List [ List [ int ]]: res = [] out = [ 0 ] * k i = 0 while i >= 0 : out [ i ] += 1 if out [ i ] > n : i -= 1 elif i == k - 1 : res . append ( list ( out )) else : i += 1 out [ i ] = out [ i - 1 ] return res ############ class Solution ( object ): def combine ( self , n , k ): if k == 1 : return [[ i ] for i in range ( 1 , n + 1 )] elif k == n : return [[ i for i in range ( 1 , n + 1 )]] else : rs = [] rs += self . combine ( n - 1 , k ) part = self . combine ( n - 1 , k - 1 ) for ls in part : ls . append ( n ) rs += part return rsVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.