Leetcode - Partition to K Equal Sum Subsets (Python)

[@dolorhunter5684]

Add "if nums[0] > partsum: return False" between line 8 & 9, improving from 5% faster than others to 95%.

[@timc3406]

For transparency here was my first approach, I got the backtracking solution from the forums n,s = len(nums),sum(nums) if s%k!=0: return False each = sum(nums)//k nums.sort(reverse=True) def dfs(arr,i): if i>=n: if all([a==each for a in arr]): return True return False for j in range(len(arr)): if arr[j]+nums[i]

[@abhishek_ar97]

Can't we try a 0/1 knapsack with weight = sum//k after the initial conditions using tabular method. Then pop out the elements that made into the set using dp table. Then redo untill all such possible pairs are done and array is empty. This would reduce the complexity

[@edwardteach2]

Time Complexity - O(2^n) , Space - O(n) for those who might be asking Brilliant to issue the reset, wouldn't have thought about it - if cur_sum == part_sum: return dfs(kleft - 1, 0, 0)