> For the complete documentation index, see [llms.txt](https://joshualbarb.gitbook.io/leetcode-problems/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://joshualbarb.gitbook.io/leetcode-problems/backtracking/combinations.md).

# Combinations

## Problem

Given two integers *n* and *k*, return all possible combinations of *k*numbers out of 1 ... *n*.

You may return the answer in **any order**.

{% hint style="info" %}
For example:

```
Input: n = 4, k = 2
Output:
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]
```

```
Input: n = 1, k = 1
Output: [[1]]
```

{% endhint %}

### Thought Process

![](/files/-MNJYy8nCJRg46RCv5Tp)

* The for-loops and recursion method are very similar to the Subset problem, apart from the part that stops the DFS/recursion; for this problem it's when k = 0.

* We can generate the subsets in pairs of  *k*  by decreasing *k* inside the recursion method. This is basically like saying "Hey we have 1 number (which is that specific number the for loop is on) so we can explore the other numbers in our recurrsion and while doing so, we'll decrease k."

## Solution

```
class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        soln = [] 
        self.helper(n,k,1,soln,[])
        return soln
    
    def helper(self, n, k, index, soln, subset):
        
        if k == 0:
            soln.append(list(subset))
        
        for i in range(index, n+1):
            subset.append(i)
            self.helper(n, k-1, i+1, soln, subset)
            subset.pop()
```

## Key Points

* The for-loop is the important factor that helps us traverse the "branches" for each number.

* We are decreasing *k* in our recursion method which helps us keep track of how many numbers we can append to the subset list still.

## Time Complexity

![](/files/-MNJbwalDPUHLismsk9I)

* **Time:** $$O((N!/(N-k)! \* k!) \* k)$$ because of the combination formula and we multiply that by k because of our operation of copying the list in k time (since there is only k elements in the combination list)

* **Space:** $$O(N-k)$$ because this will be the max depth of the  recursion call stack