Skip to content

Instantly share code, notes, and snippets.

@mamaz
Last active March 30, 2020 20:03
Show Gist options
  • Save mamaz/4cf0789e36097842a2ddb4bbcbb0d9c1 to your computer and use it in GitHub Desktop.
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
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