n数之和

leetcode 1 号算法题：两数之和 (哈希表时间O(n),空间O(n))
leetcode 167 号算法题：两数之和Ⅱ - 输入有序数组 (二分 O(nlogn)，O(1) 双指针O(n)， O(1))
leetcode 170 号算法题：两数之和Ⅲ - 数据结构设计
leetcode 653 号算法题：两数之和Ⅳ - 输入 BST (由于是BST，中序遍历+双指针或哈希)
leetcode 15 号算法题：三数之和 （排序+双指针 O(n^2)， O(1)）
剑指 Offer II 007. 数组中和为 0 的三个数 （排序+双指针 O(n^2)， O(1)）
leetcode 18 号算法题：四数之和

暴力

递归遍历k个元素组合的全排列模板
剑指 Offer II 080. 含有 k 个元素的组合
给定两个整数 n 和 k，返回 1 … n 中所有可能的 k 个数的组合。

res = []
path = []
def dfs(idx):
	if len(path) == k:
		res.append(path[:])
		return 
	if idx == n+1:
		return 
	dfs(idx+1)
	path.append(idx)
	dfs(idx+1)
	path.pop()
dfs(1)

时间复杂度O(2的n次方)：每个数字都有两种选择，空间复杂度O(n)，为递归深度

之后，我们可以根据所有的组合可能来筛选出k的元素之和

双指针、三指针

排序+二分查找

#先来个快排，或者直接用sort
# O(nlog(n))
def quick_sort(l,r):
	if l>=r:
		return 
	i,j = l,r
	mid = num[l]
	while num[j] >= mid:
		j -=1
	num[l],num[r] = num[r],num[l]
	while num[i]<=mid:
		i+=1
	num[l],num[r] = num[r],num[l]
	quick_sort(l,i)
	quick_sort(i+1,r)
quick_sort(0,len(nums)-1)
#二分查找
#两数之和直接二分，O(n)
#三数之和类似，循环第一位然后再二分，O（n^2）
#这里以三数之和为例
res = []
#O(n)
for i in range(len(nums)-2):
	l,r = i+1, len(nums)-1
	# O(n)
	while l<r:
		if nums[r] + nums[l] < target - nums[i]:
			l+=1
		elif nums[r] + nums[l] > target - nums[i]:
			r-=1
		else:
			if [nums[i],nums[l],nums[r]] not in res:
				res.append([nums[i],nums[l],nums[r]])
			l+=1
			r-=1
return res