Last active
March 30, 2020 20:03
-
-
Save mamaz/4cf0789e36097842a2ddb4bbcbb0d9c1 to your computer and use it in GitHub Desktop.
sum from List, checksum(0, [2,4,8], 6) -> True, checksum(0, [2,4,8], 15) -> False
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
from typing import List | |
def checksum(acc: int, lst: List[int], exist_total: int)-> bool: | |
sorted_nums = sorted(lst) | |
return checksum_rec(sorted_nums, exist_total, exist_total) | |
def checksum_rec(nums: List, exist_total: int, orig_total: int)->int: | |
if len(nums) == 0 and exist_total > 0: | |
return False | |
else: | |
top_value = nums.pop() | |
# handles top value larger than original total | |
if orig_total < top_value: | |
return checksum_rec(nums, orig_total, orig_total) | |
temp = exist_total-top_value | |
if temp in nums: | |
return True | |
# handle minus from substraction | |
if temp < 0: | |
nums.append(top_value) | |
return checksum_rec(nums, orig_total, orig_total) | |
if temp == 0: | |
return True | |
return checksum_rec(nums, temp, orig_total) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment