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