Python: Given an array of non negative numbers and a total, is there subset of numbers in this array which adds up to given total. — """ * Time complexity is O(input.size * total_sum) * Space complexity is O(input.size*total_sum) """ def subset_sum(sequence, sum_value): cols = sum_value + 1 # Plus 1 for 0 valued col. rows = len(sequence) + 1 # Plus 1 for 0 valued row. T = [[False for _ in range(cols)] for _ in range(rows)] for row in range(rows): T[row][0] = True for index_i in range(1, rows): for index_j in range(1, cols): if index_j >= sequence[index_i - 1]: T[index_i][index_j] = T[index_i - 1][index_j] or T[index_i - 1][index_j - sequence[index_i - 1]] else: T[index_i][index_j] = T[index_i - 1][index_j] return T[rows - 1][cols - 1] if __name__ == '__main__': sequence = [2, 3, 7, 8] assert True == subset_sum(sequence, 11)