[已解决]Python：每日一题 280

zltzlt

今天的题目：

给定一个数组 num 和一个整数 target，找到 num 中所有的数字之和为 target 的组合。

注意：组合在原列表中可以是不连续的。

示例 1：

输入：num = [7,1,2,5,1,6,10], target = 8
输出：[[1,1,6],[1,2,5],[1,7],[2,6]]

示例 2:

输入：num = [1,1,1], target = 2
输出：[[1,1]]
解释：组合列表中不能包含重复的组合。

欢迎大家一起答题！

最佳答案

月排行榜 / 总排行榜

阴阳神万物主

2019-11-25 23:18:16

但愿别超过最大递归深度
另外，真的不要求列表顺序哦？

1. def solve(num:list,target:int)->list:
   
2.     num = sorted(num,reverse=True)
   
3.     res = []
   
4.     for i in range(len(num)):
   
5.         if target > num[i]:
   
6.             now = [num[i]]
   
7.             get = solve(num[i+1:],target - num[i])
   
8.             #print('调试',num[i],target,get,num,now,res)
   
9.             for each in get:
   
10.                 each.extend(now)
    
11.                 res.append(each[:]) if each not in res else ''
    
12.         elif target == num[i]:
    
13.             res.append([num[i]]) if [num[i]] not in res else ''
    
14.     return res
    
15. 
    
16. if __name__ == '__main__':
    
17.     print('示例1 输出：',solve([7,1,2,5,1,6,10],8))
    
18.     print('示例2 输出：',solve([1,1,1],2))
    

复制代码

跳转到最佳答案楼层

凌九霄

#list不大的话，可以凑合用下

1. import itertools
   
2. 
   
3. 
   
4. def func280(L, n):
   
5.     t, result = [], []
   
6.     for i in range(1, len(L) + 1):
   
7.         t.extend(map(tuple, map(sorted, itertools.combinations(L, i))))
   
8. 
   
9.     for i in set(t):
   
10.         if sum(i) == n:
    
11.             result.append(list(i))
    
12.     return result

复制代码

peicd

除了全排列之外想不出更高效的方法。

danteer

1. import itertools
   
2. 
   
3. def func(num,target):
   
4.     if num == []:
   
5.         return []
   
6.     result = []
   
7.     num.sort()
   
8.     position = len(num)
   
9.     for i in range(len(num)):
   
10.         if num[i] > target:
    
11.             position = i
    
12.             break
    
13.     num = num[:position]
    
14.     count = 1
    
15.     while sum(num[:count]) <= target:
    
16.         temp = list(itertools.combinations(num,count))
    
17.         for each in temp:
    
18.             if sum(each) == target:
    
19.                 if not list(each) in result:
    
20.                     result.append(list(each))
    
21.         count += 1
    
22.     return result

复制代码

上面的大概超时，试试下面的吧 。。。

1. import sys
   
2. sys.setrecursionlimit(922337580)
   
3. 
   
4. def solve(num,target):
   
5.     if num == []:
   
6.         return []
   
7.     result = []
   
8.     num.sort()
   
9.     position = len(num)
   
10.     for i in range(len(num)):
    
11.         if num[i] > target:
    
12.             position = i
    
13.             break
    
14.     num = num[:position]
    
15.     count = 1
    
16.    
    
17.     def sumplus(course):
    
18.         temp = 0
    
19.         for each in course:
    
20.             temp += num[each]
    
21.         return temp
    
22.    
    
23.     def move(x,target,count,course):
    
24.         if x != len(course)-1:
    
25.             if course[x+1] != course[x] + 1:
    
26.                 course[x] += 1
    
27.                 for each in range(x+1,len(course)):
    
28.                     course[each] = course[x] + each - x
    
29.                 move(len(course)-1,target,count,course)
    
30.             else:
    
31.                 course[x] += 1
    
32.                 for i in range(x+1,len(course)):
    
33.                     course[i] = course[x] + i - x
    
34.                 move(x+1,target,count,course)
    
35.             
    
36.         else:
    
37.             ccc = sumplus(course)
    
38.             if ccc == target:
    
39.                 listtemp = []
    
40.                 for each in course:
    
41.                     listtemp.append(num[each])
    
42.                 if not listtemp in result:
    
43.                     result.append(listtemp)
    
44.                 if course[0] != len(num) - count:
    
45.                     if course[x] != len(num) - 1:
    
46.                         course[x] += 1
    
47.                         move(x,target,count,course)
    
48.                     else:
    
49.                         if len(course) > 1:
    
50.                             move(x-1,target,count,course)
    
51.                         else:
    
52.                             pass
    
53.                 else:
    
54.                     pass
    
55.             elif ccc < target:
    
56.                 if course[-1] != len(num) - 1:
    
57.                     course[-1] += 1
    
58.                     move(x,target,count,course)
    
59.                 else:
    
60.                     if course[0] == len(num) - count:
    
61.                         pass
    
62.                     else:
    
63.                         for i in range(len(course)-2,-1,-1):
    
64.                             if course[i] != len(num) - count + i:
    
65.                                 temp = i
    
66.                         move(temp,target,count,course)
    
67.             elif ccc > target:
    
68.                 if course[0] == len(num) - count:
    
69.                     pass
    
70.                 else:
    
71.                     temp = -10
    
72.                     for i in range(len(course)-2,-1,-1):
    
73.                         if course[i] != len(num) - count + i:
    
74.                             if temp == -10:
    
75.                                 temp = i
    
76.                     if temp == -10:
    
77.                         pass
    
78.                     else:
    
79.                         move(temp,target,count,course)
    
80. 
    
81.            
    
82.                  
    
83.     def comb(num,count,target):
    
84.         course = []
    
85.         for i in range(count):
    
86.             course.append(i)
    
87.         if sum(num[:count]) == target:
    
88.             temp2 = []
    
89.             for each in course:
    
90.                 temp2.append(num[each])
    
91.             result.append(temp2)
    
92.         move(len(course)-1,target,count,course)
    
93.    
    
94.     while sum(num[:count]) <= target:
    
95.         comb(num,count,target)
    
96.         count += 1
    
97.     return result

复制代码

超过最大递归深度了，白给
还是itertools好用

阴阳神万物主

但愿别超过最大递归深度
另外，真的不要求列表顺序哦？

1. def solve(num:list,target:int)->list:
   
2.     num = sorted(num,reverse=True)
   
3.     res = []
   
4.     for i in range(len(num)):
   
5.         if target > num[i]:
   
6.             now = [num[i]]
   
7.             get = solve(num[i+1:],target - num[i])
   
8.             #print('调试',num[i],target,get,num,now,res)
   
9.             for each in get:
   
10.                 each.extend(now)
    
11.                 res.append(each[:]) if each not in res else ''
    
12.         elif target == num[i]:
    
13.             res.append([num[i]]) if [num[i]] not in res else ''
    
14.     return res
    
15. 
    
16. if __name__ == '__main__':
    
17.     print('示例1 输出：',solve([7,1,2,5,1,6,10],8))
    
18.     print('示例2 输出：',solve([1,1,1],2))
    

复制代码

peicd

貌似有几位大佬假定list和target全为正整数，但题目并没有说正整数，负数也有可能哦。

Stubborn

peicd 发表于 2019-11-25 21:55
除了全排列之外想不出更高效的方法。

应该想，怎么去优化全排

CommonName

你们都好聪明啊

Stubborn

需要测试很大的数组吗？

1. def fun280(nums:List[int], target:int) ->List:
   
2.     if not nums: return []
   
3.     length = len(nums)
   
4.     nums.sort()
   
5.     result = []
   
6.     def combination(pointer:int, item:list, target:int):
   
7.         if target == 0:
   
8.             result.append(item)
   
9.             return
   
10.         if pointer == length or target < nums[pointer]:return
    
11.         for index in range(pointer, length):
    
12.             if index > pointer and nums[index] == nums[index-1]:continue
    
13.             combination(index+1, item+ [nums[index]], target-nums[index])
    
14.     combination(0, [], target)
    
15.     return result

复制代码

Python3005

1. import itertools
   
2. 
   
3. def check(lst, target):
   
4.         result = []
   
5.         length = len(lst)
   
6.         for num in range(2,length):
   
7.                 temp = itertools.combinations(lst, num)
   
8.                 for each in temp:
   
9.                         each = list(each)
   
10.                         each.sort()
    
11.                         if sum(each) == target and not each in result:
    
12.                                 result.append(each)
    
13.         return result

复制代码

dzqzzzh

想了好久不知道问题在哪。请大佬斧正

1. from itertools import combinations as cb
   
2. 
   
3. 
   
4. def listzzj(qj, mbz):
   
5.     for i in range(1, len(qj) + 1):
   
6.         zzj = list(cb(qj, i))
   
7.         for x in zzj:
   
8.             if sum(x) == mbz:
   
9.                 return x
   
10.                
    
11. 
    
12. num = [7,1,2,5,1,6,10]
    
13. target = 8
    
14. listzzj(num, target)
    

复制代码

凌九霄

dzqzzzh 发表于 2019-11-26 09:47
想了好久不知道问题在哪。请大佬斧正

你在迭代内使用return会终止迭代，所以最终只能得到第一个符合条件的结果

cdblsc

dzqzzzh 发表于 2019-11-26 09:47
想了好久不知道问题在哪。请大佬斧正

起码得把比target大得数给去掉？ 刚刚有人说可能有负数，还是不能去

cdblsc

dzqzzzh 发表于 2019-11-26 09:47
想了好久不知道问题在哪。请大佬斧正

你是只求一个就返回，这是个问题

cdblsc

dzqzzzh 发表于 2019-11-26 09:47
想了好久不知道问题在哪。请大佬斧正

还有没考虑是组合，不是排列，没有去重

cdblsc

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 = [7, 1, 2, 5, 1, 6, 10]
target = 8
print(listzzj(num, target))

晒肚皮的大青蛙

每日一题这个系列在哪个板块找到

776667

1. from itertools import combinations
   
2. 
   
3. def fun280(num,target):
   
4.     result = []
   
5.     for i in range(1,len(num)+1):
   
6.         for j in combinations(num,i):
   
7.             if sum(j) == target and sorted(list(j)) not in result:
   
8.                 result.append(sorted(list(j)))
   
9.     return result

复制代码

rosemary115

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-25 21:50
#list不大的话，可以凑合用下

输入 num = [29,19,14,33,11,5,9,23,23,33,12,9,25,25,12,21,14,11,20,30,17,19,5,6,6,5,5,11,12,25,31,28,31,33,27,7,33,31,17,13,21,24,17,12,6,16,20,16,22,5], target = 28 超时