[link](https://leetcode.com/problems/combinations/)

---

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

---

Initialize an empty list res to store the final list of combinations and an empty list comb to store the current combination being constructed. Define a recursive DFS function dfs(i, res, comb) that takes the current index i, the res list to store combinations, and the comb list to store the current combination. In the DFS function, first check if the length of comb is equal to k. If so, it means we have constructed a valid combination of length k. So, add a copy of comb to res, and return to backtrack. Check if i is greater than n. If so, it means we have explored all possible elements, so we should return and backtrack.

Iterate over the range from i to n+1, inclusive. For each value j in this range, add it to the comb list and call the DFS function recursively with j+1 to process the next index. After the recursive call, remove the last element from comb, effectively backtracking and exploring other possibilities. Call the DFS function initially with i=1 to start constructing the combinations. Return the final list of combinations res.

#### Solution 1

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        res, comb = [], []
        
        def dfs(i, res, comb):
            if len(comb) == k:
                res.append(comb.copy())
                return 
            if i > n:
                return 

            for j in range(i, n + 1):
                comb.append(j)
                dfs(j + 1, res, comb)
                comb.pop()
                

        dfs(1, res, comb)
        return res
        

O(T): O(C(n, k) * k)
O(S): O(k)