Why does my Dynamic Programming Approach to the SSP always work?

Question

Why does my code succeed 100% of the time? I want to generate 100 random samples of this code's output to measure the speed, but each time I run I receive 100 true outcomes and 0 false outcomes. Can someone offer me some advice?

import random
from random import randint, sample
from itertools import chain, combinations
import time

class SSP():
    def __init__(self, S=[], t=0):
        self.S = S
        self.t = t
        self.n = len(S)
        #
        self.decision = False
        self.total    = 0
        self.selected = []

    def __repr__(self):
        return "SSP instance: S="+str(self.S)+"\tt="+str(self.t)

    def random_instance(self, n, bitlength=10):
        max_n_bit_number = 2**bitlength-1
        self.S = sorted([randint(0,max_n_bit_number) for i in range(n)], reverse=True)
        self.t = randint(0,n*max_n_bit_number)
        self.n = len(self.S)

    def random_yes_instance(self, n, bitlength=10):
        max_n_bit_number = 2**bitlength-1
        self.S = sorted([randint(0,max_n_bit_number) for i in range(n)], reverse=True)
        self.t = sum(sample(self.S, randint(0,n)))
        self.n = len(self.S)

    def try_at_random(self, S, n, t):
        #if sum is 0, use empty set as our solution
        if (t == 0):
          return True
          print("Found a subset with given sum")
        #if n is 0 and sum is not 0, no solution possible
        if (n == 0 and t != 0):
          return False
          print("No subset within given sum")

        if (S[n-1] > sum):
          return instance.try_at_random(S, n-1, t)
        else:
          return instance.try_at_random(S, n-1, t) or instance.try_at_random(S, n-1, t-S[n-1])

i=0
tr = 0
fa = 0
instance = SSP()

for i in range (0, 100):
    instance.random_yes_instance(4)
    print(instance)

    start_time = time.time()

    if (instance.try_at_random(instance.S, instance.n, instance.t) == True):
      print("Found a subset with given sum")
      tr += 1
    else:
      print("No subset within given sum")
      fa += 1

    time_after = time.time() - start_time
    print ("Time taken: " +str(time_after)+"s")
    i+=1
print ("Times succeeded: ", tr)
print ("Times failed: ", fa)

Heres a sample output:

SSP instance: S=[754, 429, 232, 131]    t=131
Found a subset with given sum
Time taken: 0.0s
SSP instance: S=[954, 903, 768, 184]    t=0
Found a subset with given sum
Time taken: 0.0s
SSP instance: S=[871, 532, 495, 337]    t=0
Found a subset with given sum
Time taken: 0.0s
SSP instance: S=[1011, 837, 599, 559]   t=599
Found a subset with given sum
Time taken: 0.0s
SSP instance: S=[571, 306, 181, 121]    t=0
Found a subset with given sum
Time taken: 0.0s
SSP instance: S=[807, 284, 220, 71] t=1162
Found a subset with given sum
Time taken: 0.0s
('Times succeeded: ', 100)
('Times failed: ', 0)

Answer 1

1. I don't think sum is defined inside your method try_at_random(self, S, n, t), as mentioned in the comment about line 41.

2. Where you use "instance" in that "if" statement, do you mean "self"? I'm also not sure whether instance is defined there.

3. When you return that "or" (return instance.try_at_random(S, n-1, t) or instance.try_at_random(S, n-1, t-S[n-1])), what are you expecting? What do you get if you do a print statement before that return to see what that is evaluating to. I know you're trying to call it recursively, but between not using "self.try_at_random" and returning an "or" statement I'm not sure what that's doing.

Good luck!