| 1 | 1 | def combinations(target, size, exclude): |
| 2 | | pass |
| 2 | # Edge Case: Invalid input parameters |
| 3 | if size < 0 or target < 0: |
| 4 | return [] |
| 5 | |
| 6 | # Edge Case: Zero size cage |
| 7 | if size == 0: |
| 8 | return [[]] if target == 0 else [] |
| 9 | |
| 10 | # Available digits (1-9) excluding those in the exclude list |
| 11 | available_digits = [i for i in range(1, 10) if i not in exclude] |
| 12 | |
| 13 | # Edge Case: Not enough digits available |
| 14 | if len(available_digits) < size: |
| 15 | return [] |
| 16 | |
| 17 | # Edge Case: Sum too large for available digits |
| 18 | max_possible_sum = sum(sorted(available_digits, reverse=True)[:size]) |
| 19 | if target > max_possible_sum: |
| 20 | return [] |
| 21 | |
| 22 | # Edge Case: Sum too small for available digits |
| 23 | min_possible_sum = sum(sorted(available_digits)[:size]) |
| 24 | if target < min_possible_sum: |
| 25 | return [] |
| 26 | |
| 27 | def backtrack(start_idx, current_combination, remaining_sum): |
| 28 | # Base case: we've selected enough digits |
| 29 | if len(current_combination) == size: |
| 30 | if remaining_sum == 0: |
| 31 | result.append(sorted(current_combination)) |
| 32 | return |
| 33 | |
| 34 | # If remaining sum is too small to reach target, prune this path |
| 35 | if remaining_sum <= 0: |
| 36 | return |
| 37 | |
| 38 | # If not enough digits left to complete combination, prune this path |
| 39 | if len(current_combination) + (len(available_digits) - start_idx) < size: |
| 40 | return |
| 41 | |
| 42 | for i in range(start_idx, len(available_digits)): |
| 43 | digit = available_digits[i] |
| 44 | |
| 45 | # If current digit exceeds remaining sum, no point checking further |
| 46 | # since digits are sorted in ascending order |
| 47 | if digit > remaining_sum: |
| 48 | break |
| 49 | |
| 50 | backtrack(i + 1, current_combination + [digit], remaining_sum - digit) |
| 51 | |
| 52 | result = [] |
| 53 | backtrack(0, [], target) |
| 54 | |
| 55 | # Sort the result for consistent output |
| 56 | result.sort() |
| 57 | |
| 58 | return result |
| 59 | |
| 60 | # Handled Edge Cases: Invalid input parameters, sum too large for available digits, sum too small for available digits, not enough digits available |