def backtrack(candidat, solutii):
    if este_solutie(candidat):
        solutii.append(candidat[:])  # copie!
        return

    for optiune in genereaza_optiuni(candidat):
        if este_valid(candidat, optiune):   # pruning
            candidat.append(optiune)        # alege
            backtrack(candidat, solutii)    # explorează
            candidat.pop()                  # revino (undo)

def permutations(nums):
    result = []

    def backtrack(path, remaining):
        if not remaining:
            result.append(path[:])
            return

        for i in range(len(remaining)):
            path.append(remaining[i])
            backtrack(path, remaining[:i] + remaining[i+1:])
            path.pop()

    backtrack([], nums)
    return result

print(permutations([1, 2, 3]))
# [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]

def solve_n_queens(n):
    result = []
    board = [-1] * n  # board[row] = coloana reginei de pe rândul row

    def is_safe(row, col):
        for prev_row in range(row):
            prev_col = board[prev_row]
            # Verifică coloana și diagonalele
            if prev_col == col:
                return False
            if abs(prev_row - row) == abs(prev_col - col):
                return False
        return True

    def backtrack(row):
        if row == n:
            # Construim vizualizarea tablei
            solution = []
            for r in range(n):
                line = '.' * board[r] + 'Q' + '.' * (n - board[r] - 1)
                solution.append(line)
            result.append(solution)
            return

        for col in range(n):
            if is_safe(row, col):
                board[row] = col
                backtrack(row + 1)
                board[row] = -1

    backtrack(0)
    return result

# 4-Queens: 2 soluții
for sol in solve_n_queens(4):
    for row in sol:
        print(row)
    print()

def solve_n_queens_fast(n):
    result = []
    cols = set()
    diag1 = set()  # row - col
    diag2 = set()  # row + col

    def backtrack(row, board):
        if row == n:
            result.append(['.' * c + 'Q' + '.' * (n-c-1) for c in board])
            return

        for col in range(n):
            if col in cols or (row - col) in diag1 or (row + col) in diag2:
                continue

            cols.add(col)
            diag1.add(row - col)
            diag2.add(row + col)
            board.append(col)

            backtrack(row + 1, board)

            board.pop()
            cols.remove(col)
            diag1.remove(row - col)
            diag2.remove(row + col)

    backtrack(0, [])
    return result

def subsets(nums):
    result = []

    def backtrack(start, path):
        result.append(path[:])  # fiecare stare parțială e o submulțime validă

        for i in range(start, len(nums)):
            path.append(nums[i])
            backtrack(i + 1, path)
            path.pop()

    backtrack(0, [])
    return result

print(subsets([1, 2, 3]))
# [[], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3]]

def activity_selection(activities):
    """
    Greedy: sortăm după timp de terminare,
    alegem mereu activitatea care se termină cel mai devreme.
    """
    # Sortare după finish time
    sorted_act = sorted(activities, key=lambda x: x[1])

    selected = [sorted_act[0]]
    last_finish = sorted_act[0][1]

    for start, finish in sorted_act[1:]:
        if start >= last_finish:
            selected.append((start, finish))
            last_finish = finish

    return selected

activities = [(1, 3), (2, 5), (3, 4), (5, 7), (6, 8), (8, 9)]
print(activity_selection(activities))
# [(1, 3), (3, 4), (5, 7), (8, 9)] — 4 activități

def fractional_knapsack(weights, values, W):
    """
    Greedy: sortăm obiectele după valoare/greutate (descrescător)
    și luăm cât putem din fiecare.
    """
    n = len(weights)
    # (valoare per unitate, greutate, valoare)
    items = sorted(
        zip(values, weights),
        key=lambda x: x[0] / x[1],
        reverse=True
    )

    total_value = 0
    remaining = W

    for value, weight in items:
        if weight <= remaining:
            # Luăm tot obiectul
            total_value += value
            remaining -= weight
        else:
            # Luăm o fracțiune
            fraction = remaining / weight
            total_value += value * fraction
            remaining = 0
            break

    return total_value

w = [10, 20, 30]
v = [60, 100, 120]
print(fractional_knapsack(w, v, 50))  # 240.0

import heapq

class HuffmanNode:
    def __init__(self, char, freq):
        self.char = char
        self.freq = freq
        self.left = None
        self.right = None

    def __lt__(self, other):
        return self.freq < other.freq

def huffman_encoding(text):
    # 1. Calculăm frecvențele
    freq = {}
    for ch in text:
        freq[ch] = freq.get(ch, 0) + 1

    # 2. Construim arborele Huffman (greedy cu min-heap)
    heap = [HuffmanNode(ch, f) for ch, f in freq.items()]
    heapq.heapify(heap)

    while len(heap) > 1:
        left = heapq.heappop(heap)
        right = heapq.heappop(heap)
        merged = HuffmanNode(None, left.freq + right.freq)
        merged.left = left
        merged.right = right
        heapq.heappush(heap, merged)

    root = heap[0]

    # 3. Generăm codurile
    codes = {}
    def build_codes(node, code=""):
        if node.char is not None:
            codes[node.char] = code or "0"
            return
        build_codes(node.left, code + "0")
        build_codes(node.right, code + "1")

    build_codes(root)
    return codes

text = "abracadabra"
codes = huffman_encoding(text)
for ch, code in sorted(codes.items()):
    print(f"'{ch}': {code}")
# 'a': 0, 'b': 10, 'r': 110, 'c': 1110, 'd': 1111