面试算法题：判断数组前n-2个数加减组合是否等于a mod b

Hey there! This is a fun twist on classic subset sum problems—let's work through it together step by step.

First, Clarify the Problem #

Let's restate it to make sure we're aligned:

Given an integer array where the last two elements are a and b, determine if we can combine all elements except the last two using addition and subtraction (each element is used exactly once, either added or subtracted) such that the result equals a % b.

Note: Since we're computing a mod b, we can safely assume b ≠ 0 (division by zero is undefined in this context).

Core Insight: Transform to Subset Sum #

Let's define some variables to simplify the problem:

• nums: the array excluding the last two elements (a and b)
• target = a % b
• total_sum = sum(nums)

Any combination of +x or -x for each x in nums can be rewritten as:
sum(positive_elements) - sum(negative_elements) = target

Since sum(positive_elements) + sum(negative_elements) = total_sum, we can add these two equations together:
2 * sum(positive_elements) = total_sum + target

This simplifies to a key equation:
sum(positive_elements) = (total_sum + target) / 2

Now the problem boils down to: does there exist a subset of nums whose sum equals (total_sum + target) / 2?

Key Edge Cases to Check #

Before diving into the algorithm, we need to rule out impossible scenarios upfront:

1. If total_sum + target is odd: No solution exists (we can't get an integer subset sum from a non-even total).
2. If (total_sum + target) / 2 is negative: Impossible, since subset sums can't be negative (if the input has negative numbers, we can shift values to make them non-negative—more on that later).
3. If (total_sum + target) / 2 > total_sum: Also impossible, since a subset can't sum to more than the total of all elements.

Dynamic Programming Solution #

We can use a dynamic programming approach to solve the subset sum problem efficiently:

• Create a boolean array dp where dp[i] indicates whether a subset sum of i is achievable.
• Initialize dp[0] = True (a sum of 0 is always achievable with an empty subset).
• For each number in nums, iterate through the dp array from the back to avoid reusing the same element multiple times, updating dp[i] = dp[i] or dp[i - num].

Example Code (Python) #

def can_reach_mod(nums):
    if len(nums) < 2:
        return False  # Not enough elements for a and b
    a, b = nums[-2], nums[-1]
    if b == 0:
        return False  # Invalid mod operation
    target = a % b
    nums = nums[:-2]
    total_sum = sum(nums)
    
    # Check edge cases first
    if (total_sum + target) % 2 != 0:
        return False
    required_sum = (total_sum + target) // 2
    if required_sum < 0 or required_sum > total_sum:
        return False
    
    # Initialize DP array
    dp = [False] * (required_sum + 1)
    dp[0] = True
    
    for num in nums:
        # Iterate backwards to prevent reusing the same number multiple times
        for i in range(required_sum, num - 1, -1):
            dp[i] = dp[i] or dp[i - num]
    
    return dp[required_sum]

# Test case 1: Valid scenario
print(can_reach_mod([3, 1, 5, 3]))  # a=5, b=3, target=2. 3-1=2 → returns True
# Test case 2: Invalid scenario
print(can_reach_mod([1, 2, 5, 3]))  # target=2, no subset sums to (3+2)/2=2.5 → returns False

Handling Negative Numbers (Bonus) #

If the input array can contain negative numbers, we can adjust the approach by shifting all values to make them non-negative:

1. Find the minimum value min_num in nums.
2. Add abs(min_num) to every element in nums to make all values non-negative.
3. Adjust the required_sum by adding abs(min_num) * k, where k is the number of elements in the subset (wait, actually, a simpler way is to recalculate the total sum and required sum after shifting—this ensures we're working with non-negative values while preserving the subset sum logic).

内容的提问来源于stack exchange，提问作者John Lexus