当前位置 博文首页 > 阳阳的博客：【leetcode.77】组合
给定两个整数 n 和 k，返回 1 ... n 中所有可能的 k 个数的组合。
示例:
输入:?n = 4, k = 2
输出:
[
? [2,4],
? [3,4],
? [2,3],
? [1,2],
? [1,3],
? [1,4],
]
从1、2、3、4中选出两个数
? ? ?如果已经选了1，则需要在2、3、4中再选出一个数即可
? ? ?如果已经选了2，则需要在3、4中再选出一个数即可
? ? ?依次类推，我们可以画出这样的一个树形结构：
很明显，我们可以使用回溯思想：
首先，我们利用path集合用来保存每一条可能的路径中包含的数
那么，当我们的路径中的数等于k时，就可以结束当前的递归，即结束条件为path.size()=k
每次的递归的区别在于开始搜索的元素不同，因此设置一个start变量，用来指定每次搜索的起始元素，结束元素都是n。
通过以上的分析，我们可以得到第一版的代码：
package medium.phase1;
import java.util.ArrayList;
import java.util.List;
/**
* @author qcy
* @create 2020/09/23 00:12:20
*/
public class Number77 {
private List<List<Integer>> result = new ArrayList<>();
private List<Integer> path = new ArrayList<>();
public List<List<Integer>> combine(int n, int k) {
dfs(n, k, 1);
return result;
}
//dfs表示从start开始，在1-n中选k个数
public void dfs(int n, int k, int start) {
//终止条件,当找到k个数时,立即返回
if (path.size() == k) {
//将当前包含k个数的路径加入到结果集中
result.add(new ArrayList<>(path));
return;
}
//从起始元素开始寻找,终止元素都是n
for (int i = start; i <= n; i++) {
//将当前找到的数放进路径中
path.add(i);
//开始进入下一层中
dfs(n, k, i + 1);
//当dfs返回时,代表已经找到了k个数,则返回上一层继续寻找,因此需要移除路径末尾的元素
path.remove(path.size() - 1);
}
}
public static void main(String[] args) {
int n = 4;
int k = 2;
List<List<Integer>> combine = new Number77().combine(n, k);
System.out.println(combine);
}
}
运行测试用例，得到：
看样子结果正确，进行提交：
但是，仔细一想，还有没有地方进行优化呢？
当我们一开始选到4的时候，后续已经没有元素供我们选择了。因此，我们需要在一开始就排除这些无效的元素。
也就是我们需要设置每次搜索的最大的搜索起点，对应于以上树结构的操作叫做剪枝，即
也就是说，我们需要优化这段代码：
for (int i = start; i <= n; i++)我们使用更多的例子，来帮助设置i的上界。
当n=7，k=4时
? ? ?当路径中已经有1个数时，还需要选择3个数，因此搜索起点最大为5(如果是6的话，只有仅剩的6，7可以选，明显是不够选的)
? ? ?当路径中已经有2个数时，还需要选择2个数，因此搜索起点最大为6
? ? ?当路径中已经有3个数时，还需要选择1个数，因此搜索起点最大为7
当n=11，k=5时
? ? ?当路径中已经有1个数时，还需要选择4个数，因此搜索起点最大为8
? ? ?当路径中已经有2个数时，还需要选择3个数，因此搜索起点最大为9
? ? ?当路径中已经有3个数时，还需要选择2个数，因此搜索起点最大为10
因此可以得到：还需要选择的数+最大搜索起点=n+1
而还需要选择的数=k-当前路径中的数=k-path.size()
所以k-path.size()+最大搜索起点=n+1，整理可得：最大搜索起点=n-(k-path.size())+1
从而改造for循环为：
for (int i = start; i <= n - (k - path.size()) + 1; i++)再次提交：
可以，时间消耗上得到了很大程度的减少。
cs