推 ILoveErr: 不是有公式嗎 08/01 15:27
→ ILoveErr: 喔喔要輸出組合 我以為只要輸出幾種 08/01 15:27
→ ILoveErr: 大師 08/01 15:28
→ mikenekolove: 太早了吧 08/01 15:34
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