recursion我需要使用和不使用任何循環編寫代碼，以找到K 是給定數字的backtracking方程的所有可能解。x1+x2+x3 = K和x1 , x2, x3之間是非零正整數1 - 10。我的嘗試：public static int subSetSum(int i, int k, int A[]) { int sum = A[0] + A[1] + A[2]; int noOfSolutions = 0; if(k - sum < 0 || i >= A.length) return 0; if(k - sum == 0) { System.out.println(A[0] + " + " + A[1] + " + " + A[2]); noOfSolutions =+ 1; } noOfSolutions = subSetSum(i+1,k,A); int newA[] = A; newA[i] = A[i]+1; noOfSolutions = subSetSum(i,k,newA); return noOfSolutions;}運行代碼我只會得到一個解決方案。因此，如果嘗試找到所有解決方案，6它只會打印出來1+1+4（0沒有'解決方案）。
1 回答
翻閱古今
TA貢獻1780條經驗 獲得超5個贊
(1) 如果要添加和分配運算符是+=，而不是=+（這會將 +1 分配給 noOfSolutions）
(2) 你不需要一個新的向量，它也將是相同的（A 和 newA 它將具有相同的內存地址，因此對其中一個的更改將影響它們兩個）
(3) 你應該在遞歸調用后恢復你的堆棧更改
編輯
(4) 解決后應停止
public static int subSetSum(int i, int k, int A[]) {
int sum = A[0] + A[1] + A[2];
int noOfSolutions = 0;
if(k - sum < 0 || i >= A.length)
return 0;
if(k - sum == 0) {
System.out.println(A[0] + " + " + A[1] + " + " + A[2]);
--(1)--> noOfSolutions += 1;
--(4)--> return noOfSolutions;
}
noOfSolutions += subSetSum(i+1,k,A);
--(2)--> A[i] = A[i]+1;
noOfSolutions += subSetSum(i,k,A);
--(3)--> A[i] = A[i]-1;
return noOfSolutions;
}
例子
public static void main(String[] args) {
System.out.println(subSetSum(0, 4, new int[3]));
}
輸出
0 + 0 + 4
0 + 1 + 3
0 + 2 + 2
0 + 3 + 1
0 + 4 + 0
1 + 0 + 3
1 + 1 + 2
1 + 2 + 1
1 + 3 + 0
2 + 0 + 2
2 + 1 + 1
2 + 2 + 0
3 + 0 + 1
3 + 1 + 0
4 + 0 + 0
15
添加回答
舉報
0/150
提交
取消