The Weekly Challenge 067

Number Combinations and Letter Phone

Solutions on GitHub

Task 1: Number Combinations

Generate all combinations of n numbers chosen from 1 .. m.

Example Output

Input: m = 4, n = 2 Output: [[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]

Logic

Recursive backtracking building combinations of size n from numbers 1 to m in increasing order.

Perl Solution

ch-1.pl

sub combinations { my ($m, $n) = @_; my @result; sub rec { my ($start, @comb) = @_; if (@comb == $n) { push @result, [@comb]; return; } for my $i ($start .. $m) { rec($i + 1, @comb, $i); } } rec(1); return \@result; }

Python Solution

ch-1.py

def combinations(m: int, n: int) -> List[List[int]]: result = [] def rec(start, comb): if len(comb) == n: result.append(comb[:]); return for i in range(start, m + 1): rec(i + 1, comb + [i]) rec(1, []) return result

Task 2: Letter Phone

Given a digit string, return all possible letter combinations that the number could represent on a phone keypad.

Example Output

Input: '23' Output: ['ad', 'ae', 'af', 'bd', 'be', 'bf', 'cd', 'ce', 'cf']

Logic

Map each digit to its keypad letters and compute the Cartesian product across all input digits.

Perl Solution

ch-2.pl

sub letter_combinations { my ($s) = @_; my %phone = ('2'=>['a','b','c'], '3'=>['d','e','f'], ...); my @result = (''); for my $digit (split //, $s) { my @new; for my $res (@result) { push @new, map { $res . $_ } @{$phone{$digit}}; } @result = @new; } return @result; }

Python Solution

ch-2.py

def letter_combinations(digits: str) -> List[str]: if not digits: return [] phone = {'2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl', '6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz'} result = [''] for d in digits: result = [prefix + char for prefix in result for char in phone[d]] return result