[已解决]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

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

def solve(num:list,target:int)->list:
    num = sorted(num,reverse=True)
    res = []
    for i in range(len(num)):
        if target > num[i]:
            now = [num[i]]
            get = solve(num[i+1:],target - num[i])
            #print('调试',num[i],target,get,num,now,res)
            for each in get:
                each.extend(now)
                res.append(each[:]) if each not in res else ''
        elif target == num[i]:
            res.append([num[i]]) if [num[i]] not in res else ''
    return res

if __name__ == '__main__':
    print('示例1 输出：',solve([7,1,2,5,1,6,10],8))
    print('示例2 输出：',solve([1,1,1],2))

跳转到最佳答案楼层

凌九霄

#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

peicd

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

danteer

import itertools

def func(num,target):
    if num == []:
        return []
    result = []
    num.sort()
    position = len(num)
    for i in range(len(num)):
        if num[i] > 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

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

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[i] > target:
            position = i
            break
    num = num[:position]
    count = 1
    
    def sumplus(course):
        temp = 0
        for each in course:
            temp += num[each]
        return temp
    
    def move(x,target,count,course):
        if x != len(course)-1:
            if course[x+1] != course[x] + 1:
                course[x] += 1
                for each in range(x+1,len(course)):
                    course[each] = course[x] + each - x
                move(len(course)-1,target,count,course)
            else:
                course[x] += 1
                for i in range(x+1,len(course)):
                    course[i] = course[x] + i - x
                move(x+1,target,count,course)
            
        else:
            ccc = sumplus(course)
            if ccc == target:
                listtemp = []
                for each in course:
                    listtemp.append(num[each])
                if not listtemp in result:
                    result.append(listtemp)
                if course[0] != len(num) - count:
                    if course[x] != len(num) - 1:
                        course[x] += 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[0] == len(num) - count:
                        pass
                    else:
                        for i in range(len(course)-2,-1,-1):
                            if course[i] != len(num) - count + i:
                                temp = i
                        move(temp,target,count,course)
            elif ccc > target:
                if course[0] == len(num) - count:
                    pass
                else:
                    temp = -10
                    for i in range(len(course)-2,-1,-1):
                        if course[i] != 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[each])
            result.append(temp2)
        move(len(course)-1,target,count,course)
    
    while sum(num[:count]) <= target:
        comb(num,count,target)
        count += 1
    return result

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

阴阳神万物主

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

def solve(num:list,target:int)->list:
    num = sorted(num,reverse=True)
    res = []
    for i in range(len(num)):
        if target > num[i]:
            now = [num[i]]
            get = solve(num[i+1:],target - num[i])
            #print('调试',num[i],target,get,num,now,res)
            for each in get:
                each.extend(now)
                res.append(each[:]) if each not in res else ''
        elif target == num[i]:
            res.append([num[i]]) if [num[i]] not in res else ''
    return res

if __name__ == '__main__':
    print('示例1 输出：',solve([7,1,2,5,1,6,10],8))
    print('示例2 输出：',solve([1,1,1],2))

peicd

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

Stubborn

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

应该想，怎么去优化全排

CommonName

你们都好聪明啊

Stubborn

需要测试很大的数组吗？

def fun280(nums:List[int], 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[pointer]:return
        for index in range(pointer, length):
            if index > pointer and nums[index] == nums[index-1]:continue
            combination(index+1, item+ [nums[index]], target-nums[index])
    combination(0, [], target)
    return result

Python3005

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

dzqzzzh

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

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 = [7,1,2,5,1,6,10]
target = 8
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

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

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 超时