সাবসেট সাম ও হ্যামিল্টোনিয়ান সাইকেল ব্যাকট্র্যাকিং

import itertools
import random

def subset_sum_backtrack(nums, target):
    n = len(nums)
    node_count = 0
    found = {"subset": None}

    # suffix_sum[i] = nums[i] + nums[i+1] + ... + nums[n-1]
    # -- অর্থাৎ ইনডেক্স i থেকে শুরু করে বাকি সবগুলো এলিমেন্ট নিলে সর্বোচ্চ কত যোগ করা সম্ভব
    suffix_sum = [0] * (n + 1)
    for i in range(n - 1, -1, -1):
        suffix_sum[i] = suffix_sum[i + 1] + nums[i]

    chosen = []

    def backtrack(i, current_sum):
        nonlocal node_count
        node_count += 1
        if found["subset"] is not None:
            return
        if current_sum == target:
            found["subset"] = chosen.copy()
            return
        if i == n:
            return
        if current_sum > target:
            return  # প্রুন ১: আংশিক যোগফলই টার্গেট পার হয়ে গেছে
        if current_sum + suffix_sum[i] < target:
            return  # প্রুন ২: বাকি সবগুলো নিলেও টার্গেটে পৌঁছানো অসম্ভব
        chosen.append(nums[i])
        backtrack(i + 1, current_sum + nums[i])   # nums[i] নেওয়া
        chosen.pop()
        if found["subset"] is not None:
            return
        backtrack(i + 1, current_sum)              # nums[i] বাদ দেওয়া

    backtrack(0, 0)
    return found["subset"], node_count


def brute_force_subset_exists(nums, target):
    n = len(nums)
    for r in range(n + 1):
        for combo in itertools.combinations(nums, r):
            if sum(combo) == target:
                return True
    return False


nums = [3, 34, 4, 12, 5, 2, 9, 7, 15, 21, 1, 19]
n = len(nums)
print(f"n={n}, নেইভ স্পেস 2^n = {2**n}\n")

targets = [9, 24, 37, 100, 61]
for t in targets:
    subset, nodes = subset_sum_backtrack(nums, t)
    exists_bf = brute_force_subset_exists(nums, t)
    ok = (subset is not None) == exists_bf
    if subset is not None:
        assert sum(subset) == t
    print(f"target={t:>4} | পাওয়া গেল={str(subset):40} | নোড={nodes:>4} | ব্রুট-ফোর্সের সাথে মিলল={ok}")

# ফিক্সড সিড দিয়ে একাধিক র‍্যান্ডম ইনস্ট্যান্সে ব্রুট-ফোর্সের বিপরীতে ক্রস-চেক
random.seed(7)
print("\nর‍্যান্ডম ইনস্ট্যান্সে ব্রুট-ফোর্সের সাথে যাচাই:")
all_match = True
for trial in range(8):
    size = random.randint(4, 12)
    arr = [random.randint(1, 30) for _ in range(size)]
    tgt = random.randint(1, sum(arr))
    subset, nodes = subset_sum_backtrack(arr, tgt)
    exists_bf = brute_force_subset_exists(arr, tgt)
    ok = (subset is not None) == exists_bf
    if subset is not None:
        ok = ok and sum(subset) == tgt
    all_match = all_match and ok
    print(f"  trial {trial}: n={size:>2} target={tgt:>4} নোড={nodes:>4} (2^n={2**size:>5}) মিলল={ok}")

print("\nসবগুলো ট্রায়ালে ব্যাকট্র্যাকিং ব্রুট-ফোর্সের সাথে একমত:", all_match)

def hamiltonian_cycle(graph, n):
    node_count = 0
    path = [0]
    visited = [False] * n
    visited[0] = True
    result = {"cycle": None}

    def backtrack():
        nonlocal node_count
        node_count += 1
        if result["cycle"] is not None:
            return
        if len(path) == n:
            if graph[path[-1]][path[0]] == 1:   # শেষ শহর থেকে শুরুতে ফেরার এজ আছে কি
                result["cycle"] = path.copy() + [path[0]]
            return
        last = path[-1]
        for nxt in range(n):
            if not visited[nxt] and graph[last][nxt] == 1:
                visited[nxt] = True
                path.append(nxt)
                backtrack()
                path.pop()
                visited[nxt] = False
                if result["cycle"] is not None:
                    return

    backtrack()
    return result["cycle"], node_count


def edges_to_matrix(n, edges):
    g = [[0] * n for _ in range(n)]
    for u, v in edges:
        g[u][v] = 1
        g[v][u] = 1
    return g


def validate_cycle(graph, n, cycle):
    if cycle is None:
        return False
    if len(cycle) != n + 1 or cycle[0] != cycle[-1]:
        return False
    if sorted(cycle[:-1]) != list(range(n)):
        return False
    return all(graph[cycle[i]][cycle[i + 1]] == 1 for i in range(len(cycle) - 1))


n = 5
# গ্রাফ ১: একটি 5-সাইকেল 0-1-2-3-4-0, প্লাস একটি অতিরিক্ত কর্ড 0-2 -- হ্যামিল্টোনিয়ান সাইকেল অবশ্যই আছে
edges_with_cycle = [(0, 1), (1, 2), (2, 3), (3, 4), (4, 0), (0, 2)]
graph_with = edges_to_matrix(n, edges_with_cycle)

# গ্রাফ ২: ভার্টেক্স 4-এর ডিগ্রি মাত্র ১ (শুধু 0-এর সাথে যুক্ত)
# -- ডিগ্রি-১ ভার্টেক্স কখনো কোনো সাইকেলে থাকতে পারে না (সাইকেলে ঢোকা ও বেরোনোর জন্য কমপক্ষে ২টি এজ লাগে)
edges_without_cycle = [(0, 1), (1, 2), (2, 3), (3, 0), (0, 4)]
graph_without = edges_to_matrix(n, edges_without_cycle)

cycle1, nodes1 = hamiltonian_cycle(graph_with, n)
cycle2, nodes2 = hamiltonian_cycle(graph_without, n)

print("গ্রাফ ১ (সাইকেল থাকার কথা):", cycle1, "| নোড এক্সপ্লোরড:", nodes1)
print("  বৈধ কিনা:", validate_cycle(graph_with, n, cycle1))

print("\nগ্রাফ ২ (সাইকেল না থাকার কথা):", cycle2, "| নোড এক্সপ্লোরড:", nodes2)
print("  সঠিকভাবে 'নেই' রিপোর্ট করল:", cycle2 is None)