✨今日算法一题
文章目录
组合
题目描述
思路详解
本题我们的思路大体框架是枚举，通过我们几次特殊情况的判断对其进行了修改。
比如：temp 长度加上区间 [cur, n] 的长度小于 k，不可能构造出长度为 k 的 temp。
同时对其进行分情况调用函数进行递归。具体实现见代码。
代码与结果
class Solution { List<Integer> temp = new ArrayList<Integer>(); List<List<Integer>> ans = new ArrayList<List<Integer>>(); public List<List<Integer>> combine(int n, int k) { dfs(1, n, k); return ans; } public void dfs(int cur, int n, int k) { // 剪枝：temp 长度加上区间 [cur, n] 的长度小于 k，不可能构造出长度为 k 的 temp if (temp.size() + (n - cur + 1) < k) { return; } // 记录合法的答案 if (temp.size() == k) { ans.add(new ArrayList<Integer>(temp)); return; } // 考虑选择当前位置 temp.add(cur); dfs(cur + 1, n, k); temp.remove(temp.size() - 1); // 考虑不选择当前位置 dfs(cur + 1, n, k); } }
