給定一個整數陣列和number 。num
我需要寫一個函式public static int printExpr(int[] a, int num)
該函式應該列印所有可以用or運算子給出數字的組合，并回傳組合的數量。num -
解決方案應該是遞回的
例如，對于給定的陣列：
{1, 3, 6, 2}和num=4
輸出應該是：
3 1=4
6-3 1=4
2 3-1=4
2 6-3-1=4
-2 6=4
5
我的嘗試：
public static void main(String[] args) {
int[] a = {1, 3, 6, 2};
System.out.println("\n" printExpr(a, 4));
}
public static int printExpr(int[] a, int num) {
return printExpr(a, num, 0, 0, "");
}
public static int printExpr(int[] a, int num, int i, int sum, String s) {
if (i < 0 || i >= a.length)
return 0;
if (num == sum) {
System.out.println(s "=4");
return 1 printExpr(a, num, i , 0, "") ;
}
return printExpr(a, num, i 1, sum, s "") printExpr(a, num, i 1, sum a[i], s " " a[i]) printExpr(a, num, i 1, sum - a[i], s "-" a[i]) ;
}
我的輸出：
1 3=4
1-3 6=4
2
我認為這個問題有點像SubsetSum。
我錯過了什么？
注意 LinkedList,HashSet等是不允許的。
uj5u.com熱心網友回復：
首先，快速回顧一下遞回。
每個遞回實作都由兩部分組成：
基本情況- 代表一組簡單邊緣情況的部分，應該終止遞回。這些邊緣情況的結果是預先知道的。對于這個任務，第一個基本情況是達到目標總和并且必須在控制臺上列印運算式并且回傳值必須是
1（即找到一個組合）。另一個基本情況是完全發現陣列但當前總和與目標不同的情況。對于這種情況，回傳值將是0.遞回案例- 進行遞回呼叫和主要邏輯所在的方法部分。
在遞回情況下，有樹的替代執行分支：
- 我們可以忽略它；
- 貢獻目標
sum（添加到前面帶有符號的當前字串sum）； - 或從中減去它（添加到前面
sum帶有符號的當前字串并將其添加到目標）。-sum
在所有這些情況下，我們需要在1遞回呼叫方法的同時推進索引。
為了找到組合的總數，我們需要引入一個變數（在下面的代碼中表示 ）。每個遞回分支回傳的結果都將貢獻該變數。count
代碼可能如下所示：
public static int printExpression(int[] arr, int sum) {
return printExpression(arr, 0, "", sum);
}
public static int printExpression(int[] arr, int current, String expression, int sum) {
if (sum == 0) { // base case - target sum has been reached
System.out.println(expression);
return 1;
}
if (current == arr.length) { // base case - target sum wasn't reached and current index is out of bounds
return 0;
}
// recursive case
int count = 0;
count = printExpression(arr, current 1, expression, sum); // ignore current element
count = printExpression(arr, current 1, expression " " arr[current], sum - arr[current]); // add current element (i.e. subtract from the target sum)
count = printExpression(arr, current 1, expression "-" arr[current], sum arr[current]); // subtract current element (i.e. increase the target sum)
return count;
}
public static void main(String[] args) {
int combinationCount = printExpression(new int[]{1, 3, 6, 2}, 4);
System.out.println("Number of combinations: " combinationCount);
}
輸出
6-2
1 3
1-3 6
-1 3 2
-1-3 6 2
Number of combinations: 5
uj5u.com熱心網友回復：
public static int printExpr(int[] a, int num) {
return printExpr(a, num, 0, 0, "");
}
public static int printExpr(int[] a, int num, int i, int sum, String s) {
if (i < 0 || i >= a.length){
if (num == sum) {
System.out.println(s "=4");
return 1;
}
return 0;
}
if (num == sum) {
System.out.println(s "=4");
return 1;
}
return printExpr(a, num, i 1, sum, s) printExpr(a, num, i 1, sum a[i], s " " a[i]) printExpr(a, num, i 1, sum - a[i], s "-" a[i]) ;
}
輸出：
6-2=4
1 3=4
1-3 6=4
-1 3 2=4
-1-3 6 2=4
5
轉載請註明出處，本文鏈接：https://www.uj5u.com/caozuo/461007.html
上一篇：如何遞回復制陣列