07_Recursion/BacktrackingRecursion/brute_force_recursion.py - master - YamangulovAN/dz-algorithms-for-developers-python

07_Recursion/BacktrackingRecursion/brute_force_recursion.py
84 строки3 KB
Andrei Iamangulov
homework 7 на проверку
24 ноя 2025, 17:43
24 ноя 2025, 17:43f2f578f
from typing import List, Optional

#  This can be a hashtable, any structure to map 'number' to 'letters' it can manifest as
digit_to_possible_letters = ["", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"]


def order_of_release_features(numbers_of_features: List[int]) -> Optional[List[List[int]]]:
    """
    Генерирует все возможные перестановки порядка выпуска фич.

    Args:
        numbers_of_features: Список номеров фич для выпуска.

    Returns:
        Список всех возможных перестановок порядка выпуска фич или пустой список при пустом вводе.
    """
    if not numbers_of_features:
        return [[]]

    result = []

    def generate_permutations(arr, current=[]):
        if not arr:
            result.append(current)
            return

        for i in range(len(arr)):
            generate_permutations(arr[:i] + arr[i + 1:], current + [arr[i]])

    generate_permutations(numbers_of_features)
    return result


def check_powers_of_three(number: int) -> bool:
    """
    Проверяет, можно ли представить число как сумму различных степеней тройки.

    Args:
        number: Число для проверки.

    Returns:
        True если число можно представить как сумму различных степеней тройки, иначе False.
    """

    # Используем рекурсивный подход для проверки всех комбинаций степеней тройки
    def can_sum(target, power):
        if target == 0:
            return True
        if power > target or power < 0:
            return False

        # Включаем текущую степень или переходим к следующей
        return can_sum(target - power, power * 3) or can_sum(target, power * 3)

    # Начинаем с 3^0 = 1
    return can_sum(number, 1)


def possible_messages(digits: str) -> Optional[List[str]]:
    """
    Генерирует все возможные сообщения, которые могут быть набраны последовательностью цифр.

    Args:
        digits: Строка с последовательностью цифр от 2 до 9.

    Returns:
        Список всех возможных комбинаций букв или пустой список при пустом вводе.
    """
    if not digits:
        return []

    result = []

    def backtrack(index, current):
        if index == len(digits):
            result.append(current)
            return

        digit = int(digits[index])
        for letter in digit_to_possible_letters[digit]:
            backtrack(index + 1, current + letter)

    backtrack(0, "")
    return result