from collections import defaultdict, deque import random
def generate_random_subset_sum(num_elements, target_sum_range): elements = [random.randint(1, 1000) for _ in range(num_elements)] target_sum = random.randint(1, target_sum_range)
return elements, target_sum
def build_graph(elements, target_sum): graph = defaultdict(list)
for u in range(target_sum + 1):
for e in elements:
if u + e <= target_sum:
graph[u].append(u + e) return graph
def tarjan_scc(graph, n): index = 0
indices = [-1] * (n + 1) lowlink = [-1] * (n + 1) on_stack = [False] * (n + 1) stack = []
sccs = []
def strong_connect(v): nonlocal index indices[v] = index lowlink[v] = index index += 1 stack.append(v) on_stack[v] = True
for w in graph[v]:
if indices[w] == -1:
strong_connect(w)
lowlink[v] = min(lowlink[v], lowlink[w]) elif on_stack[w]:
lowlink[v] = min(lowlink[v], indices[w])
if lowlink[v] == indices[v]: scc = []
while True:
w = stack.pop() on_stack[w] = False scc.append(w)
if w == v:
break sccs.append(scc)
for v in range(n + 1): if indices[v] == -1:
strong_connect(v) return sccs

 def solve_subset_sum(elements, target_sum): graph = build_graph(elements, target_sum) sccs = tarjan_scc(graph, target_sum)
print("Graph constructed:") for u in sorted(graph.keys()):
print(f"{u}: {graph[u]}")
reachable = [False] * (target_sum + 1)
reachable[0] = True # Base case: sum of 0 is always reachable
for scc in sccs:
if any(reachable[v] for v in scc):
for v in scc: reachable[v] = True
print("Reachable sums after processing SCCs:") for i, r in enumerate(reachable):
if r:
print(i, end=' ')
print()
return reachable[target_sum]
def main():
elements = [713, 635, 466, 911, 568, 579, 820, 259, 529, 370, 785, 495, 748, 823, 702, 825, 723, 822,
142, 926, 896, 449, 292, 901, 397, 911, 146, 952, 723, 438, 537, 892, 899, 837, 75, 867, 696, 173, 834, 433, 451, 999, 986, 786, 124, 287, 758, 901, 457, 289, 3, 991, 452, 702, 134, 260, 376, 426, 764, 563, 7, 510, 341, 214, 354, 442, 467, 281, 756, 715, 482, 731, 648, 48, 998, 924, 315, 697, 209, 898, 185, 442, 52, 128, 528, 771, 308, 582, 925, 664, 605, 519, 836, 189, 597, 247, 233, 220, 147, 739]
target_sum = 4122
print(f"Elements: {elements}") print(f"Target Sum: {target_sum}")
result = solve_subset_sum(elements, target_sum) print(f"Result: {'Subset exists' if result else 'No subset exists'}")
if __name__ == "__main__": main()