陷入递归-找到最小的差异

Question

我得到了以下练习:给定一个整数数组，在递归中返回两组不同数字之间的最小绝对差值。例如:如果你有以下数组：{5,4,2}，最小的差值是1，因为如果你把它分成两组：{5}，{4,2}，你会得到: Math.abs(5-6)=1。另一个例子:如果你有以下数组：{4,3,2,1}，最小的差值是0，因为如果你把它分成两组：{4,1}，{3,2}你会得到: Math.abs(5-5)=0。这只能在递归中使用，并且您可以创建任意数量的方法。方法签名为: public static int arr(int[]minDiff)

我得到的是：

public static int minDiff(int[] arr){
    return minDiff(arr,0,0,0,arr[0]);
}
private static int minDiff(int[] arr,int index,int groupa, int groupb, int diff){
    if(index>=arr.length || arr.length-1-index<0 || (index==arr.length-1-index) ) return diff;
    int dif1=minDiff(arr,index+1,groupa+arr[index], groupb, diff);
    int dif2=minDiff(arr,index+1,groupa, groupb+arr[index], diff);
    if(Math.abs(dif1-dif2)<diff){
        diff=Math.abs(dif1-dif2);
    }
    return diff;

}

请指教

Answer 1

请看下面的代码片段

public static void main(String[] args)
{
    System.out.println(minDiff(new int[] { 5, 2, 4 })); // 1
    System.out.println(minDiff(new int[] { 5, 4, 2 })); // 1
    System.out.println(minDiff(new int[] { 1, 2, 7, 17, 6 })); // 1
    System.out.println(minDiff(new int[] { 4, 3, 2, 1 })); // 0

}

public static int minDiff(int[] arr)
{
    return minDiff(arr, 0, 0, 0);
}

private static int minDiff(int[] arr, int sumGroupA, int sumGroupB, int i)
{
    if (i == arr.length) // in case we are out of boundaries return the absolute value between the two groups
        return Math.abs(sumGroupA - sumGroupB);

    int r1 = minDiff(arr, sumGroupA + arr[i], sumGroupB, i + 1); // add to group 1
    int r2 = minDiff(arr, sumGroupA, sumGroupB + arr[i], i + 1); // add to group 2 instead

    return Math.min(r1, r2);
}