echo

任生命穿梭 时间的角落

0%

组合

Posted on In Valine:

77. 组合

给定两个整数 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],
]

以 n = 4， k = 2为例，我们可以发现如下递归结构：

  1. 如果组合里面有 1 ，那么需要在[2, 3, 4]里再找 1 个数；
  2. 如果组合里有 2 ，那么需要在[3, 4]里再找 1 个数。这里不能再包含 1 ，因为[1, 2] 这个组合已经在第一种情况中包含。

我们可以写出如下代码：

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
class Solution {
    List<List<Integer>> ans = new ArrayList<List<Integer>>();

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

    //在[start, end] 选取 k 个数
    private void dfs(int start, int end, int k, List<Integer> cur){
		// k == 0 直接返回
        if(k == 0){
            ans.add(new ArrayList<Integer>(cur));
            return;
        }
		//对每一个数进行枚举
        for(int i = 0; start + i <= end; i++){
            cur.add(start + i);
            //继续在[start + i + 1, end] 范围内选取 k - 1 个数
            dfs(start + i + 1, end, k - 1, cur);
            //删除当前选取的数，重新循环
            cur.remove(cur.size() - 1);
        }
    }
}

同时我们注意到，使用ArrayList 进行删除效率很低，将其改为 ArrayDeque。在进行循环的时候，我们选取的退出条件为start + i <= end，其实还可以缩小一点，当[start + i, end] 中的元素小于 k 个时，我们可以直接退出，将该条件修改为start + i <= end - k + 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 {
    List<List<Integer>> ans = new ArrayList<List<Integer>>();

    public List<List<Integer>> combine(int n, int k) {
        dfs(1, n, k, new ArrayDeque<Integer>());
        return ans;
    }

    private void dfs(int start, int end, int k, Deque<Integer> path){

        if(k == 0){
            ans.add(new ArrayList<Integer>(path));
            return;
        }

        //当[start + i, end]范围内数字个数小于 k 个时退出循环
        for(int i = 0; start + i <= end - k + 1; i++){
            path.addLast(start + i);
            dfs(start + i + 1, end, k - 1, path);
            path.removeLast();
        }
    }
}