将一个N-Sum简化为Two Sum

Question

我最近遇到了一个很酷的算法，它可以将“在一个数组中找到n个和目标数相加的数”这类问题简化为两个和的问题。然而，我很难理解一行代码。你知道吗

def findNsum(nums, target, N, result, results):
    if len(nums) < N or N < 2 or target < nums[0]*N or target > nums[-1]*N:  # early termination
        return
    if N == 2: # two pointers solve sorted 2-sum problem
        l,r = 0,len(nums)-1
        while l < r:
            s = nums[l] + nums[r]
            if s == target:
                results.append(result + [nums[l], nums[r]])
                l += 1
                while l < r and nums[l] == nums[l-1]:
                    l += 1
            elif s < target:
                l += 1
            else:
                r -= 1
    else: # recursively reduce N
        for i in range(len(nums)-N+1):
            if i == 0 or (i > 0 and nums[i-1] != nums[i]):
                findNsum(nums[i+1:], target-nums[i], N-1, result+[nums[i]], results)

results = []
findNsum(sorted(nums), 0, 3, [], results)
return results

条件：

if i == 0 or (i > 0 and nums[i-1] != nums[i]):

对我来说没有意义。为什么我要检查if nums[i-1] != nums[i]？如果我用nums = [-1, 0, 1, 2, 2, -1, -4]来尝试，我会得到[[-4, 2, 2], [-1, -1, 2], [-1, 0, 1]]的条件。如果我把它拿出来，我会得到[[-4, 2, 2], [-1, -1, 2], [-1, 0, 1], [-1, 0, 1]]。有人能理解吗？你知道吗

干杯！你知道吗

Answer 1

条件nums[i-1] != nums[i]是避免在选择第一个元素时创建重复的解决方案，这可以在第二个示例的输出中看到。这个问题需要找到所有唯一的解决方案，而不是所有可能的解决方案，因此我们要删除第二个[-1,0,1]