# Question

Formatted question description: https://leetcode.ca/all/77.html

```
77. Combinations
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.
Example 1:
Input: n = 4, k = 2
Output:
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]
Example 2:
Input: n = 1, k = 1
Output: [[1]]
Constraints:
1 <= n <= 20
1 <= k <= n
```

# Algorithm

### DFS

Depth-first search DFS to solve, create a large set res that saves the final result, and define a small set out that saves each combination, and put one count into out each time. If the number in out reaches k, then Save out to the final result, otherwise continue to call recursion in the next layer.

### Iteration

Each time the rightmost number is incremented and stored in the result res. When the right number exceeds n, the left number is increased, and then the current array is assigned to the left number, and then incremented one by one until the leftmost number is also If n is exceeded, the loop is stopped.

For n=4, k=2, the order of traversal is as follows:

```
0 0 #initialization
1 0
1 1
1 2 #push_back
1 3 #push_back
1 4 #push_back
1 5
2 5
2 2
2 3 #push_back
2 4 #push_back
...
3 4 #push_back
3 5
4 5
4 4
4 5
5 5 #stop
```

# Code

Java