Task 1: Digits Sum
Find all N-digit numbers whose sum of digits equals S.
Example Output
N = 2, S = 4
Output: [13, 22, 31, 40]
Logic
Recursively construct N-digit numbers where the first digit is 1-9 and subsequent digits are 0-9, matching total digit sum S.
Perl Solution
ch-1.pl
sub numbers_with_sum_of_digits {
my ($N, $S) = @_;
my @results;
sub helper {
my ($n, $s, $current) = @_;
if ($n == 0) { push @results, $current if $s == 0; return; }
my $start = length($current) == 0 ? 1 : 0;
for my $d ($start .. 9) {
helper($n - 1, $s - $d, $current . $d) if $s - $d >= 0;
}
}
helper($N, $S, "");
return \@results;
}
Python Solution
ch-1.py
def numbers_with_sum_of_digits(N: int, S: int) -> List[int]:
results = []
def helper(n, s, current):
if n == 0:
if s == 0: results.append(int(current))
return
start = 1 if not current else 0
for d in range(start, 10):
if s - d >= 0:
helper(n - 1, s - d, current + str(d))
helper(N, S, "")
return results
Task 2: Palindrome Partition
Find all possible palindrome partitioning of string S.
Example Output
Input: 'aab'
Output: [['a', 'a', 'b'], ['aa', 'b']]
Logic
Backtracking algorithm trying prefix substrings; if a prefix is a palindrome, recursively partition the remaining substring.
Perl Solution
ch-2.pl
sub palindrome_partitions {
my ($s, $start, $current, $result) = @_;
if ($start == length($s)) { push @$result, [@$current]; return; }
for my $end ($start + 1 .. length($s)) {
my $sub = substr($s, $start, $end - $start);
if ($sub eq reverse($sub)) {
palindrome_partitions($s, $end, [@$current, $sub], $result);
}
}
}
Python Solution
ch-2.py
def palindrome_partitions(s: str) -> List[List[str]]:
result = []
def backtrack(start, current):
if start == len(s):
result.append(current[:]); return
for end in range(start + 1, len(s) + 1):
sub = s[start:end]
if sub == sub[::-1]:
backtrack(end, current + [sub])
backtrack(0, [])
return result