有 Java 编程相关的问题?

你可以在下面搜索框中键入要查询的问题!

java递归地确定一组数字是否包含两个总和相等的子集

我需要弄清楚如何递归地确定是否有元素的选择,使得给定一个整数列表时,所选元素的和与未选元素的和相同

比如说布景 nums = [1,3,5,3]返回true,因为子集可以是[3,3]和[1,5],这两个列表加起来是6,所以方法应该返回true。如果该子集不存在,它应该返回false

我有密码:

private static boolean canFind(int[] nums, int index, int sumOne, int sumTwo) {
    if (index == nums.length) {
        return false;
    }

    if (oneSum == twoSum) {
        return true;
    }

    if (oneSum < twoSum) {
        return canFind(nums, index + 1, sumOne + nums[index], sumTwo);
    }

    return canFind(nums, index + 1, sumOne, sumTwo + nums[index]);
}

但我不明白这为什么不起作用,甚至不明白为什么会起作用


共 (1) 个答案

  1. # 1 楼答案

    递归canFind()方法的思想是:

    • 如果我已经处理了位置index的数字,并且 到目前为止,收集了两个总和sumOnesumTwo,是否可以 用剩下的数字找到解决方案

    在详细查看代码之前,让我们进一步澄清一下这个任务(如果我理解正确的话):为了获得有效的解决方案,必须在sumOnesumTwo中计算每个数字。不允许跳过一个数字或同时计算两个总数中的一个数字

    因此,在求解过程中的任何时候,您都可以选择是在sumOne中添加当前数,还是在sumTwo中添加当前数,这就是在两个递归调用中正确执行的操作

        canFind(nums, index + 1, sumOne + nums[index], sumTwo)
    

        canFind(nums, index + 1, sumOne, sumTwo + nums[index])
    

    但这些电话有个问题。您不知道将当前数字添加到sumOnesumTwo对解决方案是否正确,因此您应该尝试两种方法,如果其中一种方法成功,则返回true。如果sumOne较小,则代码会添加到sumTwo。虽然这似乎是合理的,但并不一定能找到解决方案。所以,你应该把这部分改为

        if (canFind(nums, index + 1, sumOne + nums[index], sumTwo)) {
            // if there's some solution by adding to sumOne, we're finished.
            return true;
        } else if (canFind(nums, index + 1, sumOne, sumTwo + nums[index])) {
            // if there's some solution by adding to sumTwo, we're finished.
            return true;
        } else {
            // if both tries didn't succeed, thre's no solution 
            // starting from the given situation
            return false;
        }
    

    我们还要继续尝试数字多久?直到我们到达数组的末尾,因为我们不能漏掉任何数字

    当我们到达阵列的末端时,我们是否有解决方案?如果两个和相等,这就是一个解决方案

    因此,在尝试递归调用之前,我们应该检查数组的结尾:

        if (index == nums.length) {
            if (sumOne == sumTwo) {
                return true;
            } else {
                return false;
            }
        }
    

    总而言之:

    private static boolean canFind(int[] nums, int index, int sumOne, int sumTwo) {
        if (index == nums.length) {
            // if we're at the end of the array, we can compare the sums
            // to decide whether this is a solution.
            if (sumOne == sumTwo) {
                return true;
            } else {
                return false;
            }
        }
        if (canFind(nums, index + 1, sumOne + nums[index], sumTwo)) {
            // if there's some solution by adding to sumOne, we're finished.
            return true;
        } else if (canFind(nums, index + 1, sumOne, sumTwo + nums[index])) {
            // if there's some solution by adding to sumTwo, we're finished.
            return true;
        } else {
            // if both tries didn't succeed, thre's no solution 
            // starting from the given situation
            return false;
        }
    }
    

    这基本上可以完成任务