---
layout: post
title: LeetCode 77
category: 技术
tags: LeetCode Medium
keywords: LeetCode
description: 2019 每天一道题 #77
---

#### 77. [Combinations](https://leetcode.com/problems/combinations/)
---
Given two integers *n* and *k*, return all possible combinations of k numbers out of *1* ... *n*.

**Example:**
```
Input: n = 4, k = 2
Output:
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]
```
#### Thoughts
---
The requirement is easy to understand, we count from *1* to *n* within *k* numbers.

**First try:**
```Java
class Solution {
    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> res = new ArrayList<>();
        if (n == 0 || k == 0 || k > n)
            return res;
        combieHelper(res, new ArrayList<>(), n, 0, k);
        return res;
    }

    private static void combineHelper(List<List<Integer>> res, List<Integer> tmp, int max, int start, int remain) {
        if (remain == 0)
            res.add(new ArrayList<>(tmp));
        else {
            for (int i = start + 1; i <= max; i++) {
                tmp.add(i);
                combieHelper(res, tmp, max, i, remain - 1);
                tmp.remove(tmp.size() - 1);
            }
        }
    }
}
```

**Result 1:**
> Runtime: **28 ms**, faster than **57.69%** of Java online submissions for Combinations.

The result is just fine, may take sometime to see how others solve this question.

**Second try:**


**Result 2:**

