# Combinations
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/combinations)
Canonical: https://scaleengineer.com/dsa/problems/combinations
**Patterns:** [Backtracking](https://scaleengineer.com/dsa/patterns/backtracking)
**Companies:** [Adobe](https://scaleengineer.com/companies/adobe), [Amazon](https://scaleengineer.com/companies/amazon), [Apple](https://scaleengineer.com/companies/apple), [Bloomberg](https://scaleengineer.com/companies/bloomberg), [Google](https://scaleengineer.com/companies/google), [Meta](https://scaleengineer.com/companies/meta), [Microsoft](https://scaleengineer.com/companies/microsoft)
---
## Problem
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 <= 20`
* `1 <= k <= n`

# Approaches
## Brute Force: Generate All Subsets and Filter
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.
**Time:** O(n * 2^n) · **Space:** O(k)
**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.
### Explanation
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.

```java
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;
    }
}
```
### Algorithm
- Initialize an empty list `result` to store the final combinations.
- The total number of subsets of `n` elements is `2^n`. We can iterate through all numbers from `0` to `2^n - 1`.
- Each number `i` in this range can be treated as a bitmask of length `n`.
- For each bitmask `i`:
  - Create a new empty list `currentCombination`.
  - Iterate from `j = 0` to `n-1`.
  - If the `j`-th bit of `i` is `1` (checked using `(i >> j) & 1`), it signifies that the number `j+1` is part of the subset. Add `j+1` to `currentCombination`.
- After constructing the subset, check if `currentCombination.size()` is equal to `k`.
- If it is, add `currentCombination` to the `result` list.
- After checking all `2^n` bitmasks, return the `result` list.

## Recursive Backtracking
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.
**Time:** O(k * C(n, k)) · **Space:** O(k)
**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`).
### Explanation
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.

```java
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);
        }
    }
}
```
### Algorithm
- Initialize an empty list `result` to store the final combinations.
- Define a recursive helper function, `backtrack(start, currentCombination)`.
- **Base Case:** If the size of `currentCombination` equals `k`, a valid combination has been found. Add a copy of `currentCombination` to `result` and return.
- **Recursive Step:** Iterate with a loop from `i = start` to `n`.
  - **Choose:** Add the current number `i` to `currentCombination`.
  - **Explore:** Make a recursive call `backtrack(i + 1, currentCombination)`. Passing `i + 1` ensures that for the next level, we only pick numbers greater than `i`, which prevents duplicate elements and duplicate combinations (e.g., we generate `[1, 2]` but not `[2, 1]`).
  - **Unchoose (Backtrack):** Remove the number `i` from `currentCombination`. 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]`.
- Start the process by calling `backtrack(1, new ArrayList<>())`.

# Solutions
### CSharp

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

### Java

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

### CPP

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

```

### Python

```python
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 rs
```