【leetcode.77】组合

梦里梦外; 2022-12-09 15:56 189阅读 0赞

## 一、题目描述 ##

给定两个整数 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中再选出一个数即可

依次类推，我们可以画出这样的一个树形结构：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMzNTkxOTAz_size_16_color_FFFFFF_t_70][]

很明显，我们可以使用回溯思想：

首先，我们利用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);
        }
    }

运行测试用例，得到：

![20200923001237938.png][]

看样子结果正确，进行提交：

![20200923001322554.png][]

但是，仔细一想，还有没有地方进行优化呢？

当我们一开始选到4的时候，后续已经没有元素供我们选择了。因此，**我们需要在一开始就排除这些无效的元素**。

也就是我们需要设置每次搜索的最大的搜索起点，对应于以上树结构的操作叫做剪枝，即

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMzNTkxOTAz_size_16_color_FFFFFF_t_70 1][]

也就是说，我们需要优化这段代码：

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++)

再次提交：

![20200923004831810.png][]

可以，时间消耗上得到了很大程度的减少。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMzNTkxOTAz_size_16_color_FFFFFF_t_70]: /images/20221123/c7d5d60726ab4d419a4bf32a9aa3b5ae.png
[20200923001237938.png]: /images/20221123/e032297a664e4f40aff49201015e6cf4.png
[20200923001322554.png]: /images/20221123/eff718b3f6084355bf0dbd18403ee32e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMzNTkxOTAz_size_16_color_FFFFFF_t_70 1]: /images/20221123/448bd43e07f741ee9de10cbb8efdc4e4.png
[20200923004831810.png]: /images/20221123/79ddd9a397fc4d3aa2f5f511b46bf0b6.png