Fantasy
0%

Leetcode 77-组合

发表于
本文字数： 1.6k 阅读时长 ≈ 1 分钟

题意

给定两个整数 $n$ 和 $k$，返回 $1\cdots n$ 中所有可能的 $k$ 个数的组合。

示例：

1
2
3
4
5
6
7
8
9
10
输入: n = 4, k = 2
输出:
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

思路

  1. DFS + 回溯

    搜索起点为 $1\cdots n - k + 1$，控制搜索树最大深度为 $k$，树中值为 $i$ 的子节点为 $[i+1, n]$。

    代码如下：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    class Solution {
    public:

        void dfs(vector<vector<int>> &ans, vector<int> &v, int n, int k, int cur) {
            v.push_back(cur);
            if (v.size() == k) {
                ans.push_back(v);
            }
            else {
                for (int i = cur + 1; i <= n; i++) {
                    dfs(ans, v, n, k, i);
                    v.pop_back();
                }
            }
        }

        vector<vector<int>> combine(int n, int k) {
            vector<vector<int>> ans;
            vector<int> cbs;
            if (k == 0 || k > n) {
                return ans;
            }
            for (int i = 1; i + k - 1 <= n; i++) {
                dfs(ans, cbs, n, k, i);
                cbs.clear();
            }
            return ans;
        }
    };

  2. 利用公式 $C_n^k=C_{n-1}^k+C_{n-1}^{k-1}$

    从 $1\cdots n$ 中选 $k$ 个数只包含两种情况：

    1. 这 $k$ 个数中包含 $n$ ，还需从剩下 $n-1$ 个数中选出 $k-1$ 个，方案数为 $C_{n-1}^{k-1}$ 。
    2. 这 $k$ 个数中不包含 $n$ ，还需从剩下 $n-1$ 个数中选出 $k$ 个，方案数为 $C_{n-1}^k$。

    因此可递归求解，代码如下：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    class Solution {
    public:
        vector<vector<int>> combine(int n, int k) {
            vector<vector<int>> ans;
            
            if (k == 0 || k > n) {
                return ans;
            }
            if (k == 1) {
                for (int i = 1; i <= n; i++) {
                    vector<int> cbs;
                    cbs.push_back(i);
                    ans.push_back(cbs);
                }
                return ans;
            }
            if (k == n) {
                vector<int> cbs;
                for (int i = 1; i <= n; i++)
                    cbs.push_back(i);
                ans.push_back(cbs);
                return ans;
            }

            ans = combine(n - 1, k);
            vector<vector<int>> tmp = combine(n - 1, k - 1);
            for (int i = 0; i < tmp.size(); i++) {
                tmp[i].push_back(n);
                ans.push_back(tmp[i]);
            }

            return ans;
        }
    };