Re: [閒聊] 每日LeetCode已回收
https://leetcode.com/problems/combinations/
77. Combinations
給你一個數字 n 和 k ，返回 Cnk 的組合。
Example 1:
Input: n = 4, k = 2
Output: [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]
Explanation: There are 4 choose 2 = 6 total combinations.
Note that combinations are unordered, i.e., [1,2] and [2,1] are considered to
be the same combination.
Example 2:
Input: n = 1, k = 1
Output: [[1]]
Explanation: There is 1 choose 1 = 1 total combination.
思路：
1.回溯法經典題，dfs窮舉所有可能的結果，並做一些剪枝後返回。
Java Code：
----------------------------------------------------
class Solution {
private List<List<Integer>> res;
public List<List<Integer>> combine(int n, int k) {
res = new ArrayList<>();
dfs(new ArrayList<>(), n, k, 1);
return res;
}
private void dfs(List<Integer> curr, int n, int k, int start) {
if (k < 0) {
return;
}
if (k == 0) {
res.add(new ArrayList<>(curr));
return;
}
for (int i = start; i <= n; i++) {
curr.add(i);
dfs(curr, n, k - 1, i + 1);
curr.remove(curr.size() - 1);
}
}
}
----------------------------------------------------
--
https://i.imgur.com/4nfnn6f.jpg
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 122.100.75.86 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1690874774.A.60B.html
推
08/01 15:27,
2年前
, 1F
08/01 15:27, 1F
→
08/01 15:27,
2年前
, 2F
08/01 15:27, 2F
→
08/01 15:28,
2年前
, 3F
08/01 15:28, 3F
→
08/01 15:34,
2年前
, 4F
08/01 15:34, 4F
討論串 (同標題文章)
完整討論串 (本文為第 386 之 719 篇)：