The Weekly Challenge 065

Digits Sum and Palindrome Partition

Solutions on GitHub

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