Subsequence of Size K With the Largest Even Sum - Solution & Explanation

Problem Overview: You are given an integer array and an integer k. Select a subsequence of exactly k elements such that their total sum is even and as large as possible. If no such subsequence exists, return -1.

Approach 1: Brute Force Enumeration (Exponential Time)

Generate every subsequence of size k, compute its sum, and track the largest sum that is even. This can be implemented using recursion or bitmask enumeration. The method checks C(n, k) combinations, giving O(C(n,k) * k) time complexity and O(k) auxiliary space for the current subset. It works only for very small arrays and is mainly useful for validating logic or understanding the constraint that the final sum must be even.

Approach 2: Greedy + Sorting (O(n log n))

The optimal strategy starts by sorting the array in descending order so the largest values are considered first. Select the top k numbers and compute their sum. If the sum is already even, this is the best possible result because replacing any element would reduce the total. If the sum is odd, adjust the selection using parity swaps.

Track the smallest odd and smallest even number inside the chosen k elements, and the largest odd and largest even number outside the selection. To fix an odd sum, perform one of two swaps: replace a chosen odd with an outside even, or replace a chosen even with an outside odd. Both swaps flip the parity of the total sum. Compute the resulting sums for both options and choose the larger valid even sum. Sorting dominates the runtime, giving O(n log n) time and O(1) extra space beyond the sort.

This approach works because parity is the only constraint preventing the maximum sum. By keeping the best candidates for odd-even swaps, you adjust the parity with the smallest possible loss in value.

Recommended for interviews: Interviewers expect the Greedy + Sorting solution. The brute force explanation shows you understand the constraint space, but recognizing that parity can be fixed with a minimal swap demonstrates strong reasoning with arrays, greedy algorithms, and sorting. The final solution runs in O(n log n) and handles all edge cases cleanly.