【題目】*216. 組合總和 III
找出所有相加之和為 n 的 k 個數的組合，組合中只允許含有 1 - 9 的正整數，并且每種組合中不存在重復的數字，
說明：
所有數字都是正整數，
解集不能包含重復的組合，
示例 1:
輸入: k = 3, n = 7
輸出: [[1,2,4]]
示例 2:
輸入: k = 3, n = 9
輸出: [[1,2,6], [1,3,5], [2,3,4]]
【解題思路1】回溯剪枝
class Solution {
public List<List<Integer>> combinationSum3(int k, int n) {
List<List<Integer>> ans = new ArrayList<>();
if(k > 9 || n < (1 + k) * k / 2 || n > (19 - k) * k / 2) return ans;
List<Integer> path = new ArrayList<>();
dfs(1, k, n, ans, path);
return ans;
}
public void dfs(int start, int k, int n, List<List<Integer>> ans, List<Integer> path) {
if(n < 0) return;
if(k == 0 && n == 0) {
ans.add(new ArrayList<>(path));
return;
}
for(int i = start; i < 10; i++) {
path.add(i);
dfs(i + 1, k - 1, n - i, ans, path);
path.remove(path.size() - 1);
}
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/22026.html
標籤：java
上一篇：GNU Radio系列教程（七）：初級篇之GNU Radio GRC PSK調制解調
下一篇：FFmpeg 踩坑記錄