| 1 | 1 | def combinations(target: int, size: int, exclude: list[int]) -> list[list[int]]: |
| 2 | | pass |
| 2 | # Edge Case: Invalid size (non-positive or too large) |
| 3 | if size <= 0 or size > 9: |
| 4 | return [] |
| 5 | |
| 6 | # Edge Case: Invalid target sum (impossible to achieve with given size) |
| 7 | min_possible_sum = sum(range(1, size + 1)) |
| 8 | max_possible_sum = sum(range(9 - size + 1, 10)) |
| 9 | if target < min_possible_sum or target > max_possible_sum: |
| 10 | return [] |
| 11 | |
| 12 | # Edge Case: Too many excluded digits leaving insufficient digits to form a cage |
| 13 | available_digits = [d for d in range(1, 10) if d not in exclude] |
| 14 | if len(available_digits) < size: |
| 15 | return [] |
| 16 | |
| 17 | def backtrack(start_idx, current_combination, remaining_sum): |
| 18 | # Base case: Found a valid combination |
| 19 | if len(current_combination) == size: |
| 20 | if remaining_sum == 0: |
| 21 | result.append(list(current_combination)) |
| 22 | return |
| 23 | |
| 24 | # Pruning: Not enough digits left to complete the combination |
| 25 | if len(current_combination) + (len(available_digits) - start_idx) < size: |
| 26 | return |
| 27 | |
| 28 | # Pruning: Remaining sum is too small to be achieved with remaining digits |
| 29 | if remaining_sum <= 0: |
| 30 | return |
| 31 | |
| 32 | for i in range(start_idx, len(available_digits)): |
| 33 | digit = available_digits[i] |
| 34 | |
| 35 | # Pruning: Early termination if digit is larger than remaining sum and we still need more digits |
| 36 | if digit > remaining_sum and len(current_combination) < size - 1: |
| 37 | break |
| 38 | |
| 39 | current_combination.append(digit) |
| 40 | backtrack(i + 1, current_combination, remaining_sum - digit) |
| 41 | current_combination.pop() |
| 42 | |
| 43 | result = [] |
| 44 | backtrack(0, [], target) |
| 45 | return result |
| 46 | |
| 47 | # Handled Edge Cases: Invalid size, invalid target sum, insufficient available digits, pruning for performance |