LeetCode77-组合

发表于 | 分类于

题目链接

英文链接：https://leetcode.com/problems/combinations/

中文链接：https://leetcode-cn.com/problems/combinations/

题目详述

给定两个整数 n 和 k，返回 1 … 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],
]

题目详解

DFS，回溯。

  • 每次尝试添加当前元素，然后当前元素加上 1 进入下一层。
  • 递归的终止条件是已经添加了 k 个数，将这 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
public class LeetCode_00077 {

    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> list = new ArrayList<>(k);
        dfs(n, k, 1, res, list);
        return res;
    }

    private void dfs(int n, int k, int s, List<List<Integer>> res, List<Integer> list) {
        if (list.size() == k) {
            // 传入一个深拷贝
            res.add(new ArrayList<>(list));
            return;
        }
        for (int i = s; i <= n; ++i) {
            // 添加当前元素
            list.add(i);
            dfs(n, k, i + 1, res, list);
            // 恢复
            list.remove(list.size() - 1);
        }
    }
}
  • 由于最终的 list.size() 要等于 k，达不到要求可以进行剪枝优化。
  • 即 n - i + 1 >= k - list.size()，i <= n - (k - list.size()) + 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
public class LeetCode_00077 {

    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> list = new ArrayList<>(k);
        dfs(n, k, 1, res, list);
        return res;
    }

    private void dfs(int n, int k, int s, List<List<Integer>> res, List<Integer> list) {
        if (list.size() == k) {
            // 传入一个深拷贝
            res.add(new ArrayList<>(list));
            return;
        }
        for (int i = s, e = n - (k - list.size()) + 1; i <= e; ++i) {   // 剪枝优化
            // 添加当前元素
            list.add(i);
            dfs(n, k, i + 1, res, list);
            // 恢复
            list.remove(list.size() - 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
public class LeetCode_00077 {

    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> res = new ArrayList<>();
        int[] p = new int[k];
        int i = 0;
        while (i >= 0) {
            ++p[i];
            if (p[i] > n) {
                --i;
            } else if (i == k - 1) {
                List<Integer> list = new ArrayList<>(k);
                for (int t : p) {
                    list.add(t);
                }
                res.add(list);
            } else {
                ++i;
                p[i] = p[i - 1];
            }
        }
        return res;
    }
}