共计 658 个字符,预计需要花费 2 分钟才能阅读完成。
LeetCode–组合
<!– more –>
博客阐明
文章所波及的材料来自互联网整顿和集体总结,意在于集体学习和教训汇总,如有什么中央侵权,请分割自己删除,谢谢!
介绍
77. 组合
题目
给定两个整数 n 和 k,返回 1 … n 中所有可能的 k 个数的组合。
示例:
输出: n = 4, k = 2
输入:
[[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]
代码
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);
}
}
感激
Leetcode
以及勤奋的本人,集体博客,GitHub
正文完