# [LeetCode 77] Combinations

### Question

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

For example,
If n = 4 and k = 2, a solution is:

```[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]
```

### Stats

 Frequency 4 Difficulty 3 Adjusted Difficulty 3 Time to use ----------

Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)

### Analysis

This is a very classic problem.

The solution is standard, and we must be able to write it without even using our brain (only use hands).

### Solution

Solution 1, recursive DFS calls.

Solution 2, nested loop. Code is shown below.

### Code

First, my DFS solution

``````public ArrayList<ArrayList<Integer>> combine(int n, int k) {
ArrayList<ArrayList<Integer>> ans = new ArrayList<ArrayList<Integer>>();
if (k == 0) return ans;
helper(ans, new ArrayList<Integer>(), n, k, 0, 0);
return ans;
}

private void helper(ArrayList<ArrayList<Integer>> ans,ArrayList<Integer> list,
int n, int k, int curPt, int preNum) {
if (curPt == k) {
return;
}
for (int i = preNum + 1; i <= n - k + 1 + curPt; i ++) {
helper(ans, list, n, k, curPt + 1, i);
list.remove(list.size() - 1);
}
}
``````

Second, my nested for-loop solution

``````public ArrayList<ArrayList<Integer>> combine(int n, int k) {
ArrayList<ArrayList<Integer>> ans = new ArrayList<ArrayList<Integer>>();
if (n == 0 || k == 0 || k > n) return ans;
ArrayList<ArrayList<Integer>> temp = null;
for (int i = 0; i < k; i ++) {
temp = new ArrayList<ArrayList<Integer>>();
for (ArrayList<Integer> a: ans) {
for (int j = 1; j <= n; j ++) {
if (a.size() > 0 && a.get(a.size() - 1) >= j)
continue;
a.remove(a.size() - 1);
}
}
ans = temp;
}
return ans;
}
``````

Updated June 14th, rewrote the code using template

``````public List<List<Integer>> combine(int n, int k) {
if (n == 0 || k == 0 || n < k) {
return ans;
}
helper(ans, new LinkedList<Integer>(), n, k, 1);
return ans;
}

private void helper(List<List<Integer>> ans, List<Integer> path, int n, int k, int pos) {
if (path.size() == k) {