Open youngyangyang04 opened 3 months ago
把sum的剪枝操作放在for循环判断条件里也可以
提供下我的代码,sum在递归中算每次sum-i
class Solution {
List<List
private void backtacking(int k,int n, int startIndex){
if(path.size() == k && n==0){
result.add(new ArrayList<>(path));
return;
}
for(int i = startIndex;i<=9;i++){
path.add(i);
backtacking(k,n-i,i+1);
path.remove(path.size()-1);
}
}
}
//剪枝操作
class Solution {
List<List
private void backtacking(int k,int n, int startIndex){
if(path.size() == k && n==0){
result.add(new ArrayList<>(path));
return;
}
for(int i = startIndex;i<=9;i++){
path.add(i);
backtacking(k,n-i,i+1);
path.remove(path.size()-1);
}
}
}
private void backtracking(int n, int k, int sum, int start) {
if (sum > n) return;
if (path.size() == k) {
if (sum == n) {
paths.add(new ArrayList<>(path));
}
return;
}
for (int i = start; i <= 9 - (k - path.size()) + 1; i++) {
sum += i;
path.add(i);
backtracking(n, k, sum, i + 1);
sum -= i;
path.remove(path.size() - 1);
}
}
// 深度1: backtracking(9, 3, 0, 1), 在 1 ~ 7 中取一个数, path = []
i = 1:path = [1],递归 backtracking(9, 3, 0, 2),回溯,path = [] ...
i = 7:path = [7],递归 backtracking(9, 3, 0, 8),回溯,path = []
// 深度2: backtracking(9, 3, 0, 2~8), 在 (2~8) ~ 8 中取一个数, path = [1~7]
// 例: backtracking(9, 3, 0, 2): 在 2 ~ 8 中取一个数, path = [1]
i = 2:path = [1,2],递归 backtracking(9, 3, 0, 3),回溯,path = [1] ...
i = 8:path = [1,8],递归 backtracking(9, 3, 0, 9),回溯,path = [1]
// 深度3: backtracking(9, 3, 0, 3~9), 在 (3~9) ~ 9 中取一个数, path = [1~7,2~8]
// 例: backtracking(9, 3, 0, 3): 在 3 ~ 9 中取一个数, path = [1,2]
i = 3:path = [1,2,3],长度为 3,判断 sum 并处理,回溯,path = [1,2] ...
i = 9:path = [1,2,9],长度为 3,判断 sum 并处理,回溯,path = [1,2]
加油
Go版本
func combinationSum3(k int, n int) [][]int {
res := make([][]int, 0)
arr := make([]int, 0)
sum := 0
var backtrace func(start int)
backtrace = func(start int) {
// 找到和为n的k个数的组合
if len(arr) == k && sum == n {
// 避免arr底层数组的改变对结果造成的影响,所以copy一份
tmp := make([]int, k)
copy(tmp, arr)
res = append(res, tmp)
}
for i := start; i <= 9; i++ {
// 剪枝
// 再选一个数怎么也会超过n || 剩下的数个数不能满足了
if sum + i > n || 9 - i + 1 < k - len(arr) {
break
}
// 做选择
arr = append(arr, i)
sum += i
// 选下一个数
backtrace(i + 1)
// 撤销选择
sum -= i
arr = arr[:len(arr)-1]
}
}
// 从1开始
backtrace(1)
return res
}
https://www.programmercarl.com/0216.%E7%BB%84%E5%90%88%E6%80%BB%E5%92%8CIII.html