NSum递归实现

Given an array S of N integers, are there n elements a, b, c,d... x in S such that a + b + c + d +... + x = target? Find all unique quadruplets in the array which gives the sum of target.

Note: The solution set must not contain duplicate quadruplets.

For example, given array S = [1, 0, -1, 0, -2, 2], n = 4 and target = 0.A solution set is:[  [-1,  0, 0, 1],  [-2, -1, 1, 2],  [-2,  0, 0, 2]]
def NSum(s, t, n):	if n == 2:		return twoSum(s, t)	r = []	for i in xrange(len(s)):		rem = [x for index, x in enumerate(s) if not i==index]		ts = NSum(rem, t-s[i], n-1)		for rl in ts:			l = tuple(sorted(rl + [s[i]]))			r.append(l)	return [list(x) for x in set(r)]def twoSum(s, t):	if len(s) == 1: return []	r = {}	rs = []	for i in xrange(len(s)):		if s[i] in r:			rs.append((r[s[i]], s[i]))		else:			r[t-s[i]] = s[i]	return [list(x) for x in rs]PRint twoSum([2, 7, 3, 6], 9)print NSum([1, 0, -1, 0, -2, 2], 0, 4)