| 4 | 4 | // |
| 5 | 5 | |
| 6 | 6 | export const combinations = (cage) => { |
| 7 | | throw new Error('Remove this line and implement the function'); |
| 7 | const { sum, size, exclude } = cage; |
| 8 | |
| 9 | // Edge Case: Cage size is larger than available digits (1-9) |
| 10 | if (size > 9) return []; |
| 11 | |
| 12 | // Edge Case: Sum is impossible for the given size |
| 13 | const minSum = (size * (size + 1)) / 2; |
| 14 | const maxSum = ((9 + (9 - size + 1)) * size) / 2; |
| 15 | if (sum < minSum || sum > maxSum) return []; |
| 16 | |
| 17 | // Edge Case: Single cell cage with impossible sum |
| 18 | if (size === 1 && (sum < 1 || sum > 9)) return []; |
| 19 | |
| 20 | // Edge Case: All digits already used in constraints |
| 21 | const availableDigits = [1,2,3,4,5,6,7,8,9].filter(d => !exclude.includes(d)); |
| 22 | if (availableDigits.length < size) return []; |
| 23 | |
| 24 | const result = []; |
| 25 | |
| 26 | // Helper function to generate combinations |
| 27 | function generateCombos(remainingSum, startIndex, currentCombo) { |
| 28 | // Edge Case: Found a valid combination |
| 29 | if (remainingSum === 0 && currentCombo.length === size) { |
| 30 | result.push([...currentCombo].sort((a,b) => a-b)); |
| 31 | return; |
| 32 | } |
| 33 | |
| 34 | // Edge Case: Impossible to reach sum or too many digits |
| 35 | if (remainingSum < 0 || currentCombo.length > size) return; |
| 36 | |
| 37 | for (let i = startIndex; i < availableDigits.length; i++) { |
| 38 | const digit = availableDigits[i]; |
| 39 | |
| 40 | // Edge Case: Digit would make sum too large |
| 41 | if (digit > remainingSum) break; |
| 42 | |
| 43 | currentCombo.push(digit); |
| 44 | generateCombos(remainingSum - digit, i + 1, currentCombo); |
| 45 | currentCombo.pop(); |
| 46 | } |
| 47 | } |
| 48 | |
| 49 | // Edge Case: Empty constraint list |
| 50 | generateCombos(sum, 0, []); |
| 51 | |
| 52 | // Edge Case: Duplicate digits in existing constraints (handled by using availableDigits) |
| 53 | |
| 54 | // Sort combinations |
| 55 | return result.sort((a,b) => { |
| 56 | for (let i = 0; i < a.length; i++) { |
| 57 | if (a[i] !== b[i]) return a[i] - b[i]; |
| 58 | } |
| 59 | return 0; |
| 60 | }); |
| 8 | 61 | }; |