Subset Sum Problem with Python code

Getting Help Code Review
1

Hi everyone,

I am trying to solve this problem. I found a blog post on the subset sum problem using Python that explains the problem and provides a solution using a recursive approach. I have implemented the solution in Python, and the code is shown below.

def subset_sum(set, n, sum):
    if sum == 0:
        return True
    if n == 0:
        return False
    if set[n - 1] > sum:
        return subset_sum(set, n - 1, sum)
    return subset_sum(set, n - 1, sum) or subset_sum(set, n - 1, sum - set[n - 1])


set = [1, 2, 3, 4, 5]
n = len(set)
sum = 10

if subset_sum(set, n, sum):
    print("Yes")
else:
    print("No")

The code works by recursively checking if there is a subset of the given array whose sum is equal to the target sum. The base cases are when the sum is 0 or the array is empty. In the recursive case, we check two conditions:

  1. If the last element of the array is greater than the target sum, then we can ignore it and continue with the rest of the array.
  2. Otherwise, we can either include the last element in the subset or not include it. We do both and check if either of the cases leads to a solution.

The code outputs “Yes” if there is a subset with the desired sum, and “No” otherwise.

I would appreciate it if someone could review my code and let me know if there are any improvements that can be made.

Thanks!

2

Hi @ashnaa_roy,

This is a Go forum, hence chances are low that Pythonistas come across your post and leave helpful reviews.

Luckily, AIs aren’t as picky about programming languages as forum members are.
Here is what claude.ai says:

The recursive subset sum algorithm looks good overall. Here are a few suggestions to potentially improve it:

  • Add type annotations to make the code more readable and catch errors earlier. For example:
def subset_sum(set: List[int], n: int, sum: int) -> bool:
  • Validate the inputs upfront to catch invalid cases:
if not set or n <= 0 or n > len(set) or sum < 0:
    return False
  • Use more descriptive variable names like nums instead of set and target instead of sum:
def subset_sum(nums: List[int], n: int, target: int) -> bool:
  • Return early if the last element is greater than the target to simplify logic:
if nums[n-1] > target:
    return subset_sum(nums, n-1, target)
  • Add some comments to explain the logic and base cases

Other than these minor tweaks, the overall recursive approach looks solid. Let me know if you have any other questions!

I don’t know which of these suggestions have a point or even are correct, I am not a Pythonista. But they might be a good starting point.

1 Like