英文网站建设方法,行业网站功能,咸鱼之王小程序,网络规划设计师最新教材#x1f4dd;个人主页#xff1a;五敷有你 #x1f525;系列专栏#xff1a;算法分析与设计
⛺️稳中求进#xff0c;晒太阳 题目
给定两个整数 n 和 k#xff0c;返回范围 [1, n] 中所有可能的 k 个数的组合。
你可以按 任何顺序 返回答案。
示例
示例 1个人主页五敷有你 系列专栏算法分析与设计
⛺️稳中求进晒太阳 题目
给定两个整数 n 和 k返回范围 [1, n] 中所有可能的 k 个数的组合。
你可以按 任何顺序 返回答案。
示例
示例 1
输入n 4, k 2
输出
[[2,4],[3,4],[2,3],[1,2],[1,3],[1,4],
]
示例 2
输入n 1, k 1
输出[[1]]思路(回溯剪枝) 如果解决一个问题有多个步骤每一个步骤有多种方法题目又要我们找出所有的方法可以使用回溯算法 回溯算法是在一棵树上的 深度优先遍历因为要找所有的解所以需要遍历 组合问题相对于排列问题而言不计较一个组合内元素的顺序性即 [1, 2, 3] 与 [1, 3, 2] 认为是同一个组合因此很多时候需要按某种顺序展开搜索这样才能做到不重不漏。 回溯算法首先需要画出递归树不同的树决定了不同的代码实现。下面给出了两种画树的思路。
根据搜索起点画出二叉树 既然是树形问题上的 深度优先遍历因此首先画出树形结构。例如输入n 4, k 2我们可以发现如下递归结构 如果组合里有 1 那么需要在 [2, 3, 4] 里再找 1 个数 如果组合里有 2 那么需要在 [3, 4] 里再找 1数。注意这里不能再考虑 1因为包含 1 的组合在第 1 种情况中已经包含。 依次类推后面部分省略以上描述体现的 递归 结构是在以 n 结尾的候选数组里选出若干个元素。画出递归结构如下图 说明 叶子结点的信息体现在从根结点到叶子结点的路径上因此需要一个表示路径的变量 path它是一个列表特别地path 是一个栈 每一个结点递归地在做同样的事情区别在于搜索起点因此需要一个变量 start 表示在区间 [begin, n] 里选出若干个数的组合 对于这一类问题画图帮助分析是非常重要的解题方法。
代码实现
class Solution {public ListListInteger combine(int n, int k) {ListListInteger res new ArrayList();if (k 0 || n k) {return res;}// 从 1 开始是题目的设定DequeInteger path new ArrayDeque();dfs(n, k, 1, path, res);return res;}public static void dfs(int n,int k,int begin,DequeInteger path,ListListInteger res){//递归中止条件 path长度为kif(path.size()k){res.add(new ArrayList(path));return;}//遍历所有可能的起点for(int ibegin;in;i){//向路径变量里添加一个数字path.addLast(i);dfs(n,k,i1,path,res);path.removeLast();}}
}
运行结果
