Python：每日一题 280
本帖最后由 zltzlt 于 2019-11-25 20:53 编辑今天的题目：
给定一个数组 num 和一个整数 target，找到 num 中所有的数字之和为 target 的组合。
注意：组合在原列表中可以是不连续的。
示例 1：
输入：num = , target = 8
输出：[,,,]
示例 2:
输入：num = , target = 2
输出：[]
解释：组合列表中不能包含重复的组合。
{:10_298:}欢迎大家一起答题！{:10_298:} 本帖最后由 凌九霄 于 2019-11-25 21:54 编辑
#list不大的话，可以凑合用下
import itertools
def func280(L, n):
t, result = [], []
for i in range(1, len(L) + 1):
t.extend(map(tuple, map(sorted, itertools.combinations(L, i))))
for i in set(t):
if sum(i) == n:
result.append(list(i))
return result 除了全排列之外想不出更高效的方法。 本帖最后由 danteer 于 2019-11-26 21:28 编辑
import itertools
def func(num,target):
if num == []:
return []
result = []
num.sort()
position = len(num)
for i in range(len(num)):
if num > target:
position = i
break
num = num[:position]
count = 1
while sum(num[:count]) <= target:
temp = list(itertools.combinations(num,count))
for each in temp:
if sum(each) == target:
if not list(each) in result:
result.append(list(each))
count += 1
return result
上面的大概超时，试试下面的吧{:10_277:} 。。。
import sys
sys.setrecursionlimit(922337580)
def solve(num,target):
if num == []:
return []
result = []
num.sort()
position = len(num)
for i in range(len(num)):
if num > target:
position = i
break
num = num[:position]
count = 1
def sumplus(course):
temp = 0
for each in course:
temp += num
return temp
def move(x,target,count,course):
if x != len(course)-1:
if course != course + 1:
course += 1
for each in range(x+1,len(course)):
course = course + each - x
move(len(course)-1,target,count,course)
else:
course += 1
for i in range(x+1,len(course)):
course = course + i - x
move(x+1,target,count,course)
else:
ccc = sumplus(course)
if ccc == target:
listtemp = []
for each in course:
listtemp.append(num)
if not listtemp in result:
result.append(listtemp)
if course != len(num) - count:
if course != len(num) - 1:
course += 1
move(x,target,count,course)
else:
if len(course) > 1:
move(x-1,target,count,course)
else:
pass
else:
pass
elif ccc < target:
if course[-1] != len(num) - 1:
course[-1] += 1
move(x,target,count,course)
else:
if course == len(num) - count:
pass
else:
for i in range(len(course)-2,-1,-1):
if course != len(num) - count + i:
temp = i
move(temp,target,count,course)
elif ccc > target:
if course == len(num) - count:
pass
else:
temp = -10
for i in range(len(course)-2,-1,-1):
if course != len(num) - count + i:
if temp == -10:
temp = i
if temp == -10:
pass
else:
move(temp,target,count,course)
def comb(num,count,target):
course = []
for i in range(count):
course.append(i)
if sum(num[:count]) == target:
temp2 = []
for each in course:
temp2.append(num)
result.append(temp2)
move(len(course)-1,target,count,course)
while sum(num[:count]) <= target:
comb(num,count,target)
count += 1
return result
超过最大递归深度了，白给{:10_277:}
还是itertools好用 但愿别超过最大递归深度
另外，真的不要求列表顺序哦？
def solve(num:list,target:int)->list:
num = sorted(num,reverse=True)
res = []
for i in range(len(num)):
if target > num:
now = ]
get = solve(num,target - num)
#print('调试',num,target,get,num,now,res)
for each in get:
each.extend(now)
res.append(each[:]) if each not in res else ''
elif target == num:
res.append(]) if ] not in res else ''
return res
if __name__ == '__main__':
print('示例1 输出：',solve(,8))
print('示例2 输出：',solve(,2))
本帖最后由 peicd 于 2019-11-26 00:07 编辑
貌似有几位大佬假定list和target全为正整数，但题目并没有说正整数，负数也有可能哦。 peicd 发表于 2019-11-25 21:55
除了全排列之外想不出更高效的方法。
应该想，怎么去优化全排{:10_285:} 你们都好聪明啊 本帖最后由 Stubborn 于 2019-11-26 00:49 编辑
{:10_254:}需要测试很大的数组吗？
def fun280(nums:List, target:int) ->List:
if not nums: return []
length = len(nums)
nums.sort()
result = []
def combination(pointer:int, item:list, target:int):
if target == 0:
result.append(item)
return
if pointer == length or target < nums:return
for index in range(pointer, length):
if index > pointer and nums == nums:continue
combination(index+1, item+ ], target-nums)
combination(0, [], target)
return result import itertools
def check(lst, target):
result = []
length = len(lst)
for num in range(2,length):
temp = itertools.combinations(lst, num)
for each in temp:
each = list(each)
each.sort()
if sum(each) == target and not each in result:
result.append(each)
return result 想了好久不知道问题在哪。请大佬斧正from itertools import combinations as cb
def listzzj(qj, mbz):
for i in range(1, len(qj) + 1):
zzj = list(cb(qj, i))
for x in zzj:
if sum(x) == mbz:
return x
num =
target = 8
listzzj(num, target)
本帖最后由 凌九霄 于 2019-11-26 10:31 编辑
dzqzzzh 发表于 2019-11-26 09:47
想了好久不知道问题在哪。请大佬斧正
你在迭代内使用return会终止迭代，所以最终只能得到第一个符合条件的结果 dzqzzzh 发表于 2019-11-26 09:47
想了好久不知道问题在哪。请大佬斧正
起码得把比target大得数给去掉？ 刚刚有人说可能有负数，还是不能去
dzqzzzh 发表于 2019-11-26 09:47
想了好久不知道问题在哪。请大佬斧正
你是只求一个就返回，这是个问题 dzqzzzh 发表于 2019-11-26 09:47
想了好久不知道问题在哪。请大佬斧正
还有没考虑是组合，不是排列，没有去重
dzqzzzh 发表于 2019-11-26 09:47
想了好久不知道问题在哪。请大佬斧正
from itertools import combinations as cb
def listzzj(qj, mbz):
xs=[]
for i in range(1, len(qj) + 1):
zzj = list(cb(qj, i))
for x in zzj:
if sum(x) == mbz:
x=sorted(x)
if x not in xs:
xs.append(x)
return xs
num =
target = 8
print(listzzj(num, target)) 每日一题这个系列在哪个板块找到{:5_109:} from itertools import combinations
def fun280(num,target):
result = []
for i in range(1,len(num)+1):
for j in combinations(num,i):
if sum(j) == target and sorted(list(j)) not in result:
result.append(sorted(list(j)))
return result from itertools import combinations
def fun280(num,target):
result = []
for i in range(1,len(num)+1):
for j in combinations(num,i):
if sum(j) == target and sorted(list(j)) not in result:
result.append(sorted(list(j)))
return result 本帖最后由 zltzlt 于 2019-11-26 20:56 编辑
凌九霄 发表于 2019-11-25 21:50
#list不大的话，可以凑合用下
输入 num = , target = 28 超时