Card Game: Find Three Cards Summing to 15

Problem

You are implementing a card game analyzer that operates on a matrix (grid) of cards. Each card has a numeric value, and the goal is to find all possible sets of exactly three cards whose values sum to exactly 15.

Your task is to write a function that:

1. Takes a 2D matrix of card values as input
2. Finds all valid combinations of exactly 3 cards that sum to 15
3. Returns these combinations, ensuring each card position is used at most once
4. Continues finding sets until no more valid combinations can be made with the remaining unused cards

The cards are arranged in a grid, and any three cards from anywhere in the grid can form a valid set, as long as they sum to 15 and haven't already been used in a previous set.

Requirements

1. Find all possible sets of exactly 3 cards that sum to 15
2. Each card position in the matrix can only be used once across all returned sets
3. Return the sets as a list of lists, where each inner list contains exactly 3 card values
4. If no valid sets exist, return an empty list
5. The order of sets in the result and the order of cards within each set does not matter for correctness

Constraints

• Matrix dimensions: 1 ≤ rows, cols ≤ 10
• Card values: 1 ≤ value ≤ 20
• The matrix will contain at least 3 cards total
• Time complexity: Should handle matrices up to 10×10 efficiently
• Space complexity: O(n) where n is the total number of cards

Examples

Example 1:

Input: [[2, 7, 6], [9, 5, 1], [4, 3, 8]] Output: [[2, 7, 6]] Explanation: The first row contains three cards that sum to 15 (2 + 7 + 6 = 15). This is the only valid set in the matrix.

Example 2:

` Input: [[8, 3, 4], [1, 5, 9], [6, 7, 2]] Output: [[8, 3, 4], [8, 1, 6]] or [[8, 3, 4], [9, 5, 1]] (multiple valid answers) Explanation: Multiple sets can be found:

• 8 + 3 + 4 = 15 (first row)
• 8 + 1 + 6 = 15 (using cards from different positions)
• 9 + 5 + 1 = 15 (middle row) After using cards for one set, those positions are marked as used and cannot be reused. `

Example 3:

Input: [[1, 1, 1], [2, 2, 2], [3, 3, 3]] Output: [] Explanation: No combination of three cards sums to 15. The maximum possible sum is 3 + 3 + 3 = 9.

Example 4:

Input: [[5, 5, 5], [1, 2, 3], [4, 6, 7]] Output: [[5, 5, 5]] Explanation: Three cards with value 5 (from different positions) sum to 15.

Hint 1: Flatten and Track Consider flattening the 2D matrix into a 1D list while keeping track of which positions have been used. This makes it easier to iterate through all possible combinations of three cards.

Hint 2: Combination Generation You can use itertools.combinations to generate all possible 3-card combinations from the available cards. Then check which combinations sum to 15 and mark those positions as used.

Hint 3: Greedy Strategy A greedy approach works well: repeatedly find any valid set of 3 cards that sum to 15, add it to your result, mark those positions as used, and continue until no more valid sets can be found.

Full Solution `` Explanation:

The solution uses a greedy approach with the following steps:

1. Flatten the Matrix: Convert the 2D matrix into a flat list of tuples containing (value, row, col) to make iteration easier while preserving position information.

2. Track Used Positions: Maintain a set of indices that have been used in previous sets to ensure each card is only used once.

3. Iterative Search: Use a while loop to repeatedly search for valid sets:

   • Get all currently unused card indices
   • Generate all possible 3-card combinations from unused cards
   • Check if any combination sums to 15
   • If found, add it to results and mark those positions as used
   • Repeat until no valid combinations remain

4. Combination Generation: Use itertools.combinations to efficiently generate all possible 3-card combinations without repetition.

Time Complexity: O(n³ × k) where n is the total number of cards and k is the number of sets found. For each set found, we potentially check O(n³) combinations.

Space Complexity: O(n) for storing the flattened card list and the used positions set.

This approach guarantees we find all possible non-overlapping sets that sum to 15, using each card position at most once.

from itertools import combinations

def findCardSets(matrix):
    """
    Find all possible sets of exactly 3 cards from the matrix that sum to 15.
    Each card can only be used once across all returned sets.
    
    Args:
        matrix: A 2D list of integers representing card values
        
    Returns:
        A list of lists, where each inner list contains 3 card values that sum to 15
    """
    # Flatten the matrix into a list of (value, row, col) tuples
    cards = []
    for i in range(len(matrix)):
        for j in range(len(matrix[i])):
            cards.append((matrix[i][j], i, j))
    
    # Track which positions have been used
    used = set()
    result = []
    
    # Keep finding valid sets until no more exist
    while True:
        found_set = False
        
        # Get indices of unused cards
        available_indices = [i for i in range(len(cards)) if i not in used]
        
        # Try all combinations of 3 unused cards
        for combo_indices in combinations(available_indices, 3):
            values = [cards[i][0] for i in combo_indices]
            
            # Check if this combination sums to 15
            if sum(values) == 15:
                result.append(values)
                # Mark these positions as used
                used.update(combo_indices)
                found_set = True
                break  # Found a set, restart search with remaining cards
        
        # If no set was found in this iteration, we're done
        if not found_set:
            break
    
    return result