class Solution {
// 回溯
List<List> res = new ArrayList<>(); // 结果集合
LinkedList path = new LinkedList<>();
public List<List> combinationSum3(int k, int n) {
backTracking(n, k, 1, 0);
return res;
}
public void backTracking(int targetSum, int k, int startIndex, int sum) {
// 减枝
if (sum > targetSum) {
return;
}
// 结束条件
if (path.size() == k) {
if (sum == targetSum) {
res.add(new ArrayList<>(path));
}
return;
}
// 减枝 9 - (k - path.size()) + 1
for (int i = startIndex; i <= 9 - (k - path.size()) + 1; i++) {
path.add(i);
sum += i;
backTracking(targetSum, k, i + 1, sum);
// 回溯,移除上次加入的元素
path.removeLast();
// 回溯，sum减去上次加的数字
sum -= i;
}
}
}//转换为Dart内容：class Solution {
List<List> res = []; // 结果集合
List path = [];
List<List> combinationSum3(int k, int n) {
backTracking(n, k, 1, 0);
return res;
}
void backTracking(int targetSum, int k, int startIndex, int sum) {
// 减枝
if (sum > targetSum) {
return;
}
// 结束条件
if (path.length == k) {
if (sum == targetSum) {
res.add(List.from(path));
}
return;
}
// 减枝 9 - (k - path.length) + 1
for (int i = startIndex; i <= 9 - (k - path.length) + 1; i++) {
path.add(i);
sum += i;
backTracking(targetSum, k, i + 1, sum);
// 回溯,移除上次加入的元素
path.removeLast();
// 回溯，sum减去上次加的数字
sum -= i;
}
}
}
