fork download
copy 
  1. from functools import lru_cache
  2. from typing import List
  3.  
  4. l = [100, 125, 185, 60, 195, 25]
  5.  
  6. def cache(f): return lru_cache(maxsize=None)(f)
  7.  
  8. class Solution:
  9.     def canPartition(self, nums: List[int]) -> bool:
  10.         totalSum = sum(nums) 
  11.         if totalSum % 2 == 1:
  12.             return False
  13.         @cache
  14.         def helper(index, setOne):
  15.             print(setOne, index)
  16.             if setOne < 0:
  17.                 return False
  18.             if setOne == 0:
  19.                 return True
  20.             for x in range(index, len(nums)):
  21.                 if helper(x +1, setOne - nums[x]):
  22.                     return True
  23.             return False
  24.         return helper(0,totalSum // 2)
  25.  
  26. class Solution2:
  27.     def canPartition(self, nums):
  28.         @cache
  29.         def subsetSum(s, i):
  30.             print(s, i)
  31.             if s == 0: return True
  32.             if i >= len(nums) or s < 0: return False
  33.             return subsetSum(s-nums[i], i+1) or subsetSum(s, i+1)
  34.         total_sum = sum(nums)
  35.         return total_sum & 1 == 0 and subsetSum(total_sum // 2, 0)
  36.  
  37. print(Solution2().canPartition(l))
  38. print()
  39. print(Solution().canPartition(l))
Success #stdin #stdout 0.03s 9784KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
345 0
245 1
120 2
-65 3
120 3
60 4
-135 5
60 5
35 6
60 6
120 4
-75 5
120 5
95 6
120 6
245 2
60 3
0 4
True

345 0
245 1
120 2
-65 3
60 4
-135 5
35 6
-75 5
95 6
60 3
0 4
True
https://ideone.com/y891EY
language:
Python 3 (python  3.9.5)
created:
1 year ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!