本文正在参加「Java主题月 – Java 刷题打卡」，详情查看 活动链接

一、题目描述

面试题 16.11. 跳水板

你正在使用一堆木板建造跳水板。有两种类型的木板，其中长度较短的木板长度为shorter，长度较长的木板长度为longer。你必须正好使用k块木板。编写一个方法，生成跳水板所有可能的长度

返回的长度需要从小到大排列。

示例 1

输入：
shorter = 1
longer = 2
k = 3
输出： [3,4,5,6]
解释：
可以使用 3 次 shorter，得到结果 3；使用 2 次 shorter 和 1 次 longer，得到结果 4 。以此类推，得到最终结果。

二、思路分析

来由

• 这道题很贴近我们的生活，在我们平时很多场景都会遇到组合的问题。本题考查的考点也比较简单。官网提示需要用到的技能是递归、记忆化 。
• 这两种方式都可以解决问题。递归我们这里就不掩饰了。老生常谈的问题相信算法大家都会实现也不会是很复杂的。

• 首先我们构建一棵树，根节点是空组合。然后随着数的层级的递增在每个节点下都可以挂载连个节点分别是长木板、短木板。
• 我们将上图理解成二叉树。k代表二叉树的高度。而叶子节点就是我们最终结果集 。 所以说本题我们可以根据二叉树来存储从0-k所有的结果集。但是这样内存使用上肯定很高。因为我们需要存储很多不需要的数据
• 基于二叉树的分析，我们不难发现我们 只需要叶子节点。而且二叉树叶子结点也是有顺序的。我们不难发现二叉树叶子节点中最小值就是short*k。我们定义结果集数组为result[] 。 那么我们首先记住一个结论