Python K-Sum O(n^(k-1))


  • 0
    I

    For general K-sum problem.

    def k_sum(nums, target)
    	nums.sort()
    	k = 4
    	def search(nums, l, r, k, target):
    		results = []
    		if k == 2:
    			i = l
    			j = r
    			while i < j:
    				sum = nums[i] + nums[j]
    				if i > l and nums[i] == nums[i-1]:
    					i += 1
    					continue
    				if j < r and nums[j] == nums[j+1]:
    					j -= 1
    					continue
    				if sum == target:
    					results.append([nums[i], nums[j]])
    					i += 1
    					j -= 1
    				elif sum < target:
    					i += 1
    				else:
    					j -= 1
    		else:
    			for i in range(l, len(nums) - k + 1):
    				if i > l and nums[i] == nums[i-1]:
    					continue
    				temp = search(nums, i + 1, len(nums) - 1, k - 1, target - nums[i])
    				for idx in range(len(temp)):
    					temp[idx].append(nums[i])
    				results += temp
    		return results
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.