Partition Problem Solver

# Partition Problem Solver
# by Ido Gendel, 2022
# Share and enjoy... at your own risk!

import sys
import random

def findSum(data, index, target):

    if data[index] > target:
        return False
    elif data[index] == target:
        print("Index =", index, ", Value =", data[index])
        return True

    subTarget = target - data[index]
    subScanIndex = index - 1

    # Scan through the remaining values
    while subScanIndex >= 0:
        if findSum(data, subScanIndex, subTarget):
            print("Index =", index, ", Value =", data[index])
            return True
        subScanIndex -= 1

    return False


# Create an array with random positive integers
testData = []
for n in range(random.randint(1, 40)):
    testData.append(random.randint(1, 50))

print("Original array:", testData)

if 2 > len(testData):
    print("Array too small - no solution")
    sys.exit()

dataSum = sum(testData)
if 1 == (dataSum % 2):
    print("Odd sum", dataSum, "- no solution")
    sys.exit()

halfSum = dataSum // 2
testData.sort()
print("Sorted array:", testData)
print("Sum =", dataSum, ", Looking for a subset with the sum", halfSum, "...")
if (not findSum(testData, len(testData) - 1, halfSum)):
    print("No solution found")
else:
    print("Done!")

# Example for even sum but no solution: [14, 31, 29, 17, 22, 17, 12, 21, 17]