跳转至

剑指 Offer II 080. 含有 k 个元素的组合

题目描述

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

 

示例 1:

输入: n = 4, k = 2
输出:
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

示例 2:

输入: n = 1, k = 1
输出: [[1]]

 

提示:

  • 1 <= n <= 20
  • 1 <= k <= n

 

注意：本题与主站 77 题相同： https://leetcode.cn/problems/combinations/

解法

方法一

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        res = []

        def dfs(i, n, k, t):
            if len(t) == k:
                res.append(t.copy())
                return
            for j in range(i, n + 1):
                t.append(j)
                dfs(j + 1, n, k, t)
                t.pop()

        dfs(1, n, k, [])
        return res

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> res = new ArrayList<>();
        dfs(1, n, k, new ArrayList<>(), res);
        return res;
    }

    private void dfs(int i, int n, int k, List<Integer> t, List<List<Integer>> res) {
        if (t.size() == k) {
            res.add(new ArrayList<>(t));
            return;
        }
        for (int j = i; j <= n; ++j) {
            t.add(j);
            dfs(j + 1, n, k, t, res);
            t.remove(t.size() - 1);
        }
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    vector<vector<int>> combine(int n, int k) {
        vector<vector<int>> res;
        vector<int> t;
        dfs(1, n, k, t, res);
        return res;
    }

    void dfs(int i, int n, int k, vector<int> t, vector<vector<int>>& res) {
        if (t.size() == k) {
            res.push_back(t);
            return;
        }
        for (int j = i; j <= n; ++j) {
            t.push_back(j);
            dfs(j + 1, n, k, t, res);
            t.pop_back();
        }
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
func combine(n int, k int) [][]int {
    var res [][]int
    var t []int
    dfs(1, n, k, t, &res)
    return res
}

func dfs(i, n, k int, t []int, res *[][]int) {
    if len(t) == k {
        *res = append(*res, slices.Clone(t))
        return
    }
    for j := i; j <= n; j++ {
        t = append(t, j)
        dfs(j+1, n, k, t, res)
        t = t[:len(t)-1]
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    func combine(_ n: Int, _ k: Int) -> [[Int]] {
        var res = [[Int]]()
        dfs(1, n, k, [], &res)
        return res
    }

    private func dfs(_ start: Int, _ n: Int, _ k: Int, _ current: [Int], _ res: inout [[Int]]) {
        if current.count == k {
            res.append(current)
            return
        }

        if start > n {
            return
        }

        for i in start...n {
            var newCurrent = current
            newCurrent.append(i)
            dfs(i + 1, n, k, newCurrent, &res)
        }
    }
}

评论