【Python】递归之N数之和

leetcode第一题 两数之和（medium）

想刷力扣而被第一题劝退的同学们看好了，下面就是N数之和的终极攻略，开启你的刷题之路吧。

-----------------------------华丽的分割线----------------------------

思路（直接确定递归，需要把N数之和降维成两数之和，n-2个数暴力遍历）：

• 维护一个集合（题目要求返回不重复的元组）作为ans
• 对数组排序，便于递归剪枝
• 定义递归函数
  • 确定递归函数的参数和返回值
    • 参数：nums数组，startIndex索引，rest还有几个数，target目标和，path之前的路径，ans答案集合
    • 返回值：None
  • 递归终止条件：如果rest剩余需要的数 < 2，退出递归
  • 2数之和，在startIndex之后的数组中，找到了就加入ans，没找到就啥也不干
  • N数之和，暴力遍历也需要剪枝
    • 剪枝1：此时target < 剩余数最小值 * 个数 or target > 剩余数最大值 * 个数（这就是排序的目的），就直接break，即不存在
    • 剪枝2：举个栗子：[1,1,1,2,3,4,5]重复的，计算一次1后就可以直接pass，直接从2开始

class Solution:
    def NSum(self, nums: List[int], target: int, N: int) -> List[List[int]]:
        N, target = N, target  # 获取n数和target，获取 N 数
        if not nums or len(nums) < N or N < 2: 
            return []
        nums.sort()     
        ans = set()
        self.find_sum(nums, 0, N, target, [], ans)
        return list(ans)

    def find_sum(self, nums, startIndex, rest, target, path, ans):
        if rest < 2: return  # 如果 rest == 1，不存在
        if rest == 2:  # 两数求和
            d = set()  # 维护一个集合
            for i in range(startIndex, len(nums)):
                if target - nums[i] in d:  # 当两数之和为target时，加到ans中
                    ans.add(tuple(path + [target - nums[i], nums[i]]))
                else:
                    d.add(nums[i])
        else:
            for i in range(startIndex, len(nums)):
                # 剪枝1: target比剩余数字能组成的最小值还要小 或 比能组成的最大值还要大，就可以停止循环了
                if target < nums[i] * rest or target > nums[-1] * rest: 
                    break
                # 剪枝2: 去重
                if i > startIndex and nums[i] == nums[i - 1]: 
                    continue
                # 递归
                self.find_sum(nums, i + 1, rest - 1, target - nums[i], path + [nums[i]], ans)
        return

有了以上的思路，你就可以解决2、3、4数之和了，是不是很快乐，一次解决三道题