Problem:
- Finding the sum of items which sum up to a particular number
- Use cases:
- Finding the payments which sum up to particular amount (Payroll Matching)
- Duty Drawback – income received in bank for multiple invoices – need assistance in tracing them
import sys
import threading
import csv
import math
from PyQt5.QtWidgets import (
QApplication, QWidget, QVBoxLayout, QHBoxLayout, QLabel, QLineEdit,
QTextEdit, QPushButton, QCheckBox, QMessageBox, QSpinBox, QComboBox, QFileDialog
)
from PyQt5.QtCore import Qt, pyqtSignal, QObject, QMimeData
from PyQt5.QtGui import QClipboard
from itertools import combinations, chain, product
from bisect import bisect_left
import heapq
ALGORITHMS = [
"Brute Force",
"Backtracking",
"Dynamic Programming",
"Meet in the Middle",
"Greedy",
"Approximate (FPTAS)"
]
class Worker(QObject):
result_signal = pyqtSignal(list)
finished_signal = pyqtSignal()
def __init__(self, num_list, target, var_threshold, max_pair_len, method):
super().__init__()
self.nums = num_list
self.target = target
self.variance = var_threshold
self.max_pair_len = max_pair_len
self.method = method
self._stop_flag = threading.Event()
def stop(self):
self._stop_flag.set()
def find(self):
try:
combos = []
method = self.method
if method == "Brute Force":
combos = self.bruteforce_sum()
elif method == "Backtracking":
combos = self.backtracking_sum()
elif method == "Dynamic Programming":
combos = self.dp_sum()
elif method == "Meet in the Middle":
combos = self.meet_in_middle_sum()
elif method == "Greedy":
combos = self.greedy_sum()
elif method == "Approximate (FPTAS)":
combos = self.approximate_sum()
self.result_signal.emit(combos)
except Exception as e:
self.result_signal.emit([])
finally:
self.finished_signal.emit()
def check_sum(self, s):
return abs(s - self.target) <= self.variance
# Brute force: try every subset of length <= max_pair_len
def bruteforce_sum(self):
found = []
nums = self.nums
for r in range(1, self.max_pair_len + 1):
for combo in combinations(nums, r):
if self._stop_flag.is_set(): return []
if self.check_sum(sum(combo)):
found.append(combo)
return found
# Backtracking:
def backtracking_sum(self):
result = []
def helper(start, comb, total):
if self._stop_flag.is_set(): return
if 1 <= len(comb) <= self.max_pair_len and self.check_sum(total):
result.append(tuple(comb))
if len(comb) >= self.max_pair_len or start >= len(self.nums):
return
for i in range(start, len(self.nums)):
helper(i+1, comb + [self.nums[i]], total + self.nums[i])
helper(0, [], 0)
return result
# DP: subset sums (for int inputs)
def dp_sum(self):
arr = [int(round(x)) for x in self.nums] # Only ints!
n = len(arr)
max_length = self.max_pair_len
target = int(round(self.target))
allowed_var = self.variance
combos = []
table = [{} for _ in range(n+1)]
table[0][(0,0)] = []
for i in range(1, n+1):
a = arr[i-1]
for (s, cnt), comb in table[i-1].items():
# Don't include
if (s, cnt) not in table[i]: table[i][(s, cnt)] = comb
# Include if < max length
if cnt+1 <= max_length:
ns = s + a
ncomb = comb + [self.nums[i-1]]
if (ns, cnt+1) not in table[i]:
table[i][(ns, cnt+1)] = ncomb
# Search results
for tbl in table:
for (s, cnt), comb in tbl.items():
if cnt >= 1 and self.check_sum(s):
combos.append(tuple(comb))
# Remove duplicates
unique_combos = {tuple(sorted(c)): c for c in combos}
return list(unique_combos.values())
# Meet in the middle (faster for up to 40 elements):
def meet_in_middle_sum(self):
arr = self.nums
n = len(arr)
max_len = self.max_pair_len
half = n // 2
left_arr, right_arr = arr[:half], arr[half:]
# All combos for left half (len<=max_len)
left_subs = []
for r in range(1, min(max_len, len(left_arr)) + 1):
for c in combinations(left_arr, r):
left_subs.append((c, sum(c)))
# All combos for right half (len<=max_len)
right_subs = []
for r in range(1, min(max_len, len(right_arr)) + 1):
for c in combinations(right_arr, r):
right_subs.append((c, sum(c)))
right_dict = {}
for c, s in right_subs:
llen = len(c)
if llen not in right_dict: right_dict[llen] = []
right_dict[llen].append((c, s))
results = []
for cL, sumL in left_subs:
llen = len(cL)
rem_len = max_len - llen
# Direct match in left
if self.check_sum(sumL):
results.append(cL)
for rlen in range(1, rem_len+1):
if rlen not in right_dict: continue
for cR, sumR in right_dict[rlen]:
if self._stop_flag.is_set(): return []
total_sum = sumL + sumR
if self.check_sum(total_sum):
results.append(tuple(list(cL)+list(cR)))
# Whole right side alone
for cR, sumR in right_subs:
if self.check_sum(sumR):
results.append(cR)
# Remove duplicates
unique_combos = {tuple(sorted(c)): c for c in results}
return list(unique_combos.values())
# Greedy: repeatedly take largest available
def greedy_sum(self):
arr = sorted(self.nums, key=lambda x: abs(x), reverse=True)
best = []
min_diff = float('inf')
for r in range(1, self.max_pair_len+1):
if self._stop_flag.is_set(): return []
subset = []
s = 0
last_diff = float('inf')
used = set()
for i in range(len(arr)):
if len(subset) >= r: break
if i in used: continue
if len(subset) >= self.max_pair_len: break
test_s = s + arr[i]
if abs(test_s - self.target) < abs(s - self.target):
subset.append(arr[i])
used.add(i)
s = test_s
diff = abs(s - self.target)
if diff < min_diff and self.check_sum(s):
best = subset
min_diff = diff
return [tuple(best)] if best else []
# Approximate (FPTAS): simple scaling and greedy
def approximate_sum(self):
# Scale all inputs so that rounding error is at most variance
arr = self.nums
n = len(arr)
if n == 0: return []
# Scaling: so difference per entry <= variance / n
scale = self.variance / max(n, 1)
if scale == 0: scale = 1.0
scaled_arr = [int(round(x/scale)) for x in arr]
target = int(round(self.target / scale))
max_pair = self.max_pair_len
# DP for scaled version
combos = []
table = [{} for _ in range(n+1)]
table[0][(0, 0)] = []
for i in range(1, n+1):
a = scaled_arr[i-1]
for (s, cnt), comb in table[i-1].items():
# Don't include
if (s, cnt) not in table[i]: table[i][(s, cnt)] = comb
# Include if < max length
if cnt+1 <= max_pair:
ns = s + a
ncomb = comb + [self.nums[i-1]]
if (ns, cnt+1) not in table[i]:
table[i][(ns, cnt+1)] = ncomb
# Search results
for tbl in table:
for (s, cnt), comb in tbl.items():
if cnt >= 1 and abs(s*scale - self.target) <= self.variance:
combos.append(tuple(comb))
unique_combos = {tuple(sorted(c)): c for c in combos}
return list(unique_combos.values())
class SubsetSumApp(QWidget):
def __init__(self):
super().__init__()
self.setWindowTitle("Find the numbers which sum up to particular number")
self.worker = None
self.worker_thread = None
self.results = []
self.setup_ui()
def setup_ui(self):
layout = QVBoxLayout()
# Input
layout.addWidget(QLabel("Enter numbers (comma or newline separated):"))
self.numbers_input = QTextEdit()
layout.addWidget(self.numbers_input)
# Execution method
algo_layout = QHBoxLayout()
algo_layout.addWidget(QLabel("Method:"))
self.method_box = QComboBox()
self.method_box.addItems(ALGORITHMS)
algo_layout.addWidget(self.method_box)
layout.addLayout(algo_layout)
# Target sum
target_layout = QHBoxLayout()
target_layout.addWidget(QLabel("Target sum:"))
self.target_input = QLineEdit()
self.target_input.setPlaceholderText("e.g. 100")
target_layout.addWidget(self.target_input)
layout.addLayout(target_layout)
# Variance threshold
var_layout = QHBoxLayout()
var_layout.addWidget(QLabel("Variance threshold:"))
self.variance_spin = QSpinBox()
self.variance_spin.setMinimum(0)
self.variance_spin.setMaximum(10**9)
self.variance_spin.setValue(0)
var_layout.addWidget(self.variance_spin)
layout.addLayout(var_layout)
# Max pair length
pair_layout = QHBoxLayout()
pair_layout.addWidget(QLabel("Max numbers per combination:"))
self.pair_spin = QSpinBox()
self.pair_spin.setMinimum(1)
self.pair_spin.setMaximum(20)
self.pair_spin.setValue(4)
pair_layout.addWidget(self.pair_spin)
layout.addLayout(pair_layout)
# Buttons
buttons = QHBoxLayout()
self.find_btn = QPushButton("Find Combination")
self.find_btn.clicked.connect(self.handle_find)
buttons.addWidget(self.find_btn)
self.copy_btn = QPushButton("Copy to Clipboard")
self.copy_btn.clicked.connect(self.copy_to_clipboard)
self.copy_btn.setEnabled(False)
buttons.addWidget(self.copy_btn)
self.export_btn = QPushButton("Export to CSV")
self.export_btn.clicked.connect(self.export_to_csv)
self.export_btn.setEnabled(False)
buttons.addWidget(self.export_btn)
self.stop_btn = QPushButton("Stop")
self.stop_btn.clicked.connect(self.stop_worker)
self.stop_btn.setEnabled(False)
buttons.addWidget(self.stop_btn)
layout.addLayout(buttons)
layout.addWidget(QLabel("Results:"))
self.output_box = QTextEdit()
self.output_box.setReadOnly(True)
layout.addWidget(self.output_box)
self.setLayout(layout)
def handle_find(self):
# Parse numbers
self.copy_btn.setEnabled(False)
self.export_btn.setEnabled(False)
text = self.numbers_input.toPlainText().replace(',', '\n')
try:
nums = [float(x.strip()) for x in text.splitlines() if x.strip()]
if not nums:
raise Exception()
except:
QMessageBox.critical(self, "Invalid Input", "Could not parse the numbers.")
return
try:
target = float(self.target_input.text())
except:
QMessageBox.critical(self, "Invalid Input", "Target must be a number.")
return
variance = int(self.variance_spin.value())
max_pair_len = int(self.pair_spin.value())
method = self.method_box.currentText()
self.output_box.setText("Searching (please wait)...\nYou can press Stop to cancel.")
self.find_btn.setEnabled(False)
self.stop_btn.setEnabled(True)
self.worker = Worker(nums, target, variance, max_pair_len, method)
self.worker.result_signal.connect(self.display_result)
self.worker.finished_signal.connect(self.finished_search)
self.worker_thread = threading.Thread(target=self.worker.find)
self.worker_thread.start()
def display_result(self, combos):
self.results = combos
self.copy_btn.setEnabled(bool(combos))
self.export_btn.setEnabled(bool(combos))
if not combos:
self.output_box.setText("No combinations found.")
else:
text = []
for idx, c in enumerate(combos, 1):
text.append(f"{idx}. {', '.join(str(x) for x in c)} [sum={sum(c)}]")
self.output_box.setText("\n".join(text))
def finished_search(self):
self.find_btn.setEnabled(True)
self.stop_btn.setEnabled(False)
def copy_to_clipboard(self):
if not self.results: return
text = []
for idx, c in enumerate(self.results, 1):
text.append(f"{idx}. {', '.join(str(x) for x in c)} [sum={sum(c)}]")
cb = QApplication.clipboard()
cb.setText("\n".join(text))
QMessageBox.information(self, "Copied", "Results copied to clipboard!")
def export_to_csv(self):
if not self.results: return
path, _ = QFileDialog.getSaveFileName(self, "Export to CSV", "combinations.csv", "CSV Files (*.csv)")
if not path: return
with open(path, 'w', newline='') as f:
writer = csv.writer(f)
writer.writerow(["Index", "Numbers", "Sum"])
for idx, c in enumerate(self.results, 1):
writer.writerow([idx, ", ".join(str(x) for x in c), sum(c)])
QMessageBox.information(self, "Exported", f"Results exported to {path}")
def stop_worker(self):
if self.worker:
self.worker.stop()
self.output_box.append("\nStopping...")
if __name__ == '__main__':
app = QApplication(sys.argv)
w = SubsetSumApp()
w.show()
sys.exit(app.exec_()