# 组合

<p>给定两个整数 <em>n</em> 和 <em>k</em>，返回 1 ... <em>n </em>中所有可能的 <em>k</em> 个数的组合。</p>
<p><strong>示例:</strong></p>
<pre><strong>输入:</strong>&nbsp;n = 4, k = 2<strong><br />输出:</strong>[[2,4],[3,4],[2,3],[1,2],[1,3],[1,4],]</pre>
<p>以下<span style="color:red">错误</span>的选项是？</p>

## aop

### before

```c
#include <bits/stdc++.h>
using namespace std;
```

### after

```c
int main()
{
    Solution sol;
    int n = 4;
    int k = 2;
    vector<vector<int>> res;
    res = sol.combine(n, k);
    for (auto i : res)
    {
        for (auto j : i)
            cout << j << " ";
        cout << endl;
    }
    return 0;
}

```

## 答案

```c
class Solution
{
public:
    vector<vector<int>> combine(int n, int k)
    {
        vector<int> ones(n), lib(n);
        vector<vector<int>> result;
        for (int i = 0; i < n; i++)
        {
            ones[i] = (i < k) ? 1 : 0;
            lib[i] = i + 1;
        }
        while (1)
        {
            vector<int> solution;
            bool flag = false;
            for (int i = 0; i < n; i++)
            {
                if (ones[i])
                    solution.push_back(lib[i]);
            }
            result.push_back(solution);
            int count = 0;
            for (int i = 0; i < n - 1; i++)
            {
                if (ones[i] == 1 && ones[i + 1] == 0)
                {
                    flag = true;
                    ones[i] = 0;
                    ones[i + 1] = 1;
                    for (int j = 0; j < i; j++)
                    {
                        ones[j] = count > 0 ? 1 : 0;
                    }
                    break;
                }
                else if (ones[i])
                    count++;
            }
            if (!flag)
                break;
        }

        return result;
    }
};
```
## 选项


### A

```c
class Solution
{
public:
    vector<vector<int>> combine(int n, int k)
    {
        vector<vector<int>> ans;
        vector<int> tmp;
        combineDFS(n, k, 1, tmp, ans);
        return ans;
    }
    void combineDFS(int n, int k, int level, vector<int> &tmp, vector<vector<int>> &ans)
    {
        if (tmp.size() == k)
        {
            ans.push_back(tmp);
            return;
        }
        for (int i = level; i <= n; ++i)
        {
            tmp.push_back(i);
            combineDFS(n, k, i + 1, tmp, ans);
            tmp.pop_back();
        }
    }
};
```

### B

```c
class Solution
{
public:
    vector<vector<int>> combine(int n, int k)
    {
        vector<vector<int>> result;
        int i = 0;
        vector<int> p(k, 0);
        while (i >= 0)
        {
            p[i]++;
            if (p[i] > n)
                --i;
            else if (i == k - 1)
                result.push_back(p);
            else
            {
                ++i;
                p[i] = p[i - 1];
            }
        }
        return result;
    }
};
```

### C

```c
class Solution
{
public:
    vector<vector<int>> res;
    vector<int> tmp;
    int n;

    void backtrack(vector<int> &tmp, int idx, int cnt, int k)
    {
        if (cnt == k)
        {
            res.push_back(tmp);
            return;
        }
        for (int i = idx + 1; i <= n; ++i)
        {
            tmp[cnt] = i;
            backtrack(tmp, i, cnt + 1, k);
            tmp[cnt] = 0;
        }
    }
    vector<vector<int>> combine(int n, int k)
    {
        this->n = n;
        tmp = vector<int>(k, 0);
        backtrack(tmp, 0, 0, k);
        return res;
    }
};
```