查找一个数组是否可以产生一个具有 k 个元素的和 n

Question

给定一个可能包含重复项的 int 数组。我需要查明数组是否可以生成 sum 和 k 个元素？

我现在正在尝试使用递归，但目前我没有任何进展。我在正确设置基本案例时遇到问题。

    static boolean groupSum(int[] nums, int k, int sum) {
    
            if (sum == 0)
                return true;
    
            if (k > nums.length || sum != 0)
                return false;
            if (groupSum(nums, k, sum - nums[k - k] - nums[k - k + 1] - nums[k - k + 2]))
                return true;
            if (groupSum(nums, k, sum - nums[k - k + 1] - nums[k - k + 2] - nums[k - k + 3]))
                return true;
    
            else
                return false;
    
        }

Answer 1

你的递归方法的基本情况不正确：sum == 0不是充分条件你还必须检查是否k == 0。如果 sum 是 0 但您仍然需要使用更多元素，那么结果 true 是不正确的。

方法的递归部分也有一些错误。加起来的元素数量 k 永远不会减少。

此外，您必须跟踪数组中的位置。我的意思是你需要遍历数组。在对每个元素进行迭代时，只有两个选项：应用它（递减k并从求和) 或舍弃。在这两种情况下，您都必须增加作为参数传递的 position。

这就是修复方法：

    public static boolean groupSum(int[] nums, int k, int pos, int sum) {
        if (sum == 0 && k == 0) {
            return true;
        }
        if (sum < 0) {
            return false;
        }

        boolean result = false;
        for (int i = pos; i < nums.length; i++) {
            boolean takeElement = groupSum(nums, k - 1, pos + 1, sum - nums[i]);
            boolean discardElement = groupSum(nums, k, pos + 1, sum);
            result = takeElement || discardElement;
            if (result) { // a combination that yield the target sum was found
                break;
            }
        }
        return result;
    }

如何实现此方法还有另一种选择。但是注意：它会变慢并且显着增加内存消耗。

此方法需要创建给定数组的副本，长度减 1 在每个递归方法调用中并将其作为参数传递。在此版本中，调用方法时始终使用位置 0 处的 元素，因此不需要跟踪数组中的位置。主要逻辑保持不变：新元素既可以用于贡献 sum也可以是丢弃.

public static boolean groupSum(int[] nums, int k, int sum) { if (sum == 0 && k == 0) { return true; } if (sum < 0 || nums.length == 0) { return false; } boolean takeElement = groupSum(Arrays.copyOfRange(nums, 1, nums.length), k - 1, sum - nums[0]); boolean discardElement = groupSum(Arrays.copyOfRange(nums, 1, nums.length), k, sum); return takeElement || discardElement; }

public static void main(String[] args) { // sum of 1, 2, 3, 4, 5 yields 15 - expected true System.out.println(groupSum(new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9}, 5, 0, 15)); // it's impossible with only one element - expected false System.out.println(groupSum(new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9}, 1, 0, 10)); // sum of 4, 5, 6 yields 15 - expected true System.out.println(groupSum(new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9}, 3, 0, 15)); }

输出

true false true

查找一个数组是否可以产生一个具有 k 个元素的和 n

Find if an array can produce a sum n with k number of elements

java

recursion