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

Give an int array that may contain duplicates, can the array produce a sum with k elements?

I'm trying to use recursion for now but I'm not getting anywhere at the moment, where I have a problem getting the basecase right

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;

    }

CodePudding user response：

The base case of your recursive method is incorrect: sum == 0 isn't a sufficient condition you also have to check whether k == 0. If the sum is 0 but you still have to use a few more elements then the result true is incorrect.

The recursive part of the method has some mistakes in it as well. The number of elements summed up k doesn't get decremented.

Also, you have to track a position in the array. I mean you need to iterate over the array. And while iterating for each element there are only two options: apply it (decrement the k and subtract current value from the sum) or discard it. In both cases, you have to increment the position that you are passing as an argument.

That is how it could be fixed:

    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;
    }

There's another option how to implement this method. But caution: it will be slower and significantly increases memory consumption.

This approach requires creating a copy of the given array with a length decremented by 1 at each recursive method call and pass it as an argument.

    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));
    }

output

true
false
true