Determining whether an array can be made empty by repeatedly deleting contiguous subarrays of a given length that sum to a given value

For problems where we're dealing with a sequence of operations, you can often get a dynamic programming solution by parameterizing on the first or last operation you will perform.

For our array A = [a_0, a_1, ... a_{n-1}], let's guess what the last move will be. It must be to remove k elements summing to our target, and those elements [x_0, x_1, ... x_{k-1}] form a subsequence of A which partitions the other elements of A into at most k+1 other subarrays. Before performing the last operation, the other subarrays have already been completely and individually deleted by some operations, and the subproblem on each of those subarrays is completely analogous to our original problem. This an example of optimal substructure.

Now that the framework is set up, let's talk about details. There's lots of easy edge cases: if k is 1, or if the length of the array isn't divisible by k, or if the sum of the array is incorrect, that we should check first. I'll also be assuming that target and the entries of A are nonnegative, but this can be modified with small additions to the code without affecting the runtime complexity.

What variables do our subproblems need to keep track of? There's the left and right bounds of our current array, as well as the number and sum of all the outer partition elements we've already taken. We don't know yet which k partition elements will be in the last operation-- they could be spread out over the entire original array.

We'll be walking through the array from left to right, at each point testing whether we can use the current element for that outer partition, or whether to process the next k, or 2k, or 3k, ... elements together as a contiguous subarray and continue on after that. We can filter out most subarrays from consideration: a subarray S is potentially solvable if its length is some multiple of k, m*k, and its sum is m*target. We can use prefix sums to test this quickly.

Python

def solve(arr: List[int], k: int, target: int) -> bool:
    """Decide whether arr is completely removable
    Given an array of nonnegative integers arr, a positive integer length k,
    and a nonnegative target sum, decide whether we can remove all elements
    of arr by repeatedly removing k consecutive elements summing to target.
    """
    
    assert k > 0
    assert target >= 0
    
    # This section deals with any easy edge cases
    if len(arr) % k != 0:
        return False

    if k == 1:
        return all(x == target for x in arr)

    prefixes = list(itertools.accumulate(arr, initial=0))

    if target == 0:  # Assumes target >= 0 and all values >= 0
        return prefixes[-1] == 0

    if prefixes[-1] != target * (len(arr) // k):
        return False

    if k == len(arr):
        return True


    reverse_index = collections.defaultdict(list)
    starts_to_ends = collections.defaultdict(list)  # Candidate subarrays

    for right, x in enumerate(prefixes):
        remainder = x % target
        for left in reverse_index[remainder]:
            if (right - left) % k == 0:
                if (right - left) // k == (x - prefixes[left]) // target:  # Valid sum
                    starts_to_ends[left].append(right-1)

        reverse_index[remainder].append(right)

    @functools.lru_cache(None)
    def can_solve(left: int, right, outer_need: int, outer_sum_need: int) -> bool:
        elements_remaining = right - left + 1
        
        # We've reached the end of our array
        if elements_remaining == 0:
            return outer_need == outer_sum_need == 0

        # All elements must go to the outer partition
        if elements_remaining == outer_need:
            return prefixes[right + 1] - prefixes[left] == outer_sum_need
        
        # We've used k elements for the outer partition, but
        # their sum is too small
        if outer_need == 0 and outer_sum_need != 0:
            return False
        
        # Test whether we can split into two subproblems
        for poss_ending in starts_to_ends[left]:
            if poss_ending >= right:
                break
                
            if (can_solve(left, poss_ending, 0, 0)
            and can_solve(poss_ending + 1, right, outer_need, outer_sum_need)):
                return True
        
        # We are just starting a subproblem: Initialize outer partition as empty
        # and try using current element in outer partition
        if outer_need == 0 and outer_sum_need == 0:
            if (arr[left] <= target 
            and can_solve(left + 1, right, k - 1, target - arr[left])):
                return True
            
        # Try using current element in outer partition
        if outer_need > 0 and arr[left] <= outer_sum_need:
            if can_solve(left + 1, right, outer_need - 1, outer_sum_need - arr[left]):
                return True

        return False

    return can_solve(left=0, right=len(arr) - 1, outer_need=0, outer_sum_need=0)

This can be modified to actually output the arrays to delete in order, with some more work. The current runtime is O(n^2 * target * n/k) (saving a factor of k because of our pre-filtering trick when the sum or length of an array is wrong). For many solvable arrays, a 'greedy' strategy will work and be much faster, so an optimization could be to try that first.

I believe (and have some empirical evidence) that the runtime can be brought down to O(n^2 * target), by eliminating the loop inside of the recursive function. Instead of testing all 'chunks' of the next k, or 2k, or 3k elements as a separate subproblem, it appears that you only need to test the largest such chunk whose sum is valid, although I haven't found a satisfactory proof that this always gives the right answer.

To expand on my comment: k = 2 can be handled by a linear-time greedy algorithm (push each element of A on a stack, popping the top two elements whenever they exist and sum to tar).

What makes k = 2 different is that if A contains x, y, z with x + y = tar and y + z = tar, then x = z and it doesn't matter which one we remove with y.

More formally, we show by induction on the length of A that no removal causes us to lose the ability to empty the array. This is obvious when A is empty. Inductively, suppose that all arrays shorter than A that can be emptied, can be emptied by any maximal sequence of valid removals. If A can't be emptied, then there's nothing to lose. Otherwise, we can remove some pair p and proceed to empty A. Suppose that we remove some other pair q instead. There are two cases.

1. p and q overlap. As we argued above, the resulting array will be the same, and by assumption we can empty it.

2. p and q do not overlap. Then we can get the same array by removing p then q, or q then p. By assumption and the inductive hypothesis, the former order must allow us to empty the resulting array, so the latter order is also fine.