Python：每日一题 250（答题有奖）

zltzlt

今天的题目：

找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。

说明：1. 所有数字都是正整数。
2. 解集不能包含重复的组合。
难度：★★☆☆☆

示例 1:

输入: k = 3, n = 7
输出: [[1,2,4]]

示例 2:

输入: k = 3, n = 9
输出: [[1,2,6], [1,3,5], [2,3,4]]

欢迎大家一起答题！

我的解法：

def combinationSum3(k: int, n: int):
    from itertools import combinations as c
    return list(filter(lambda x: sum(x) == n, c(range(1, 10), k)))

kaohsing

from itertools import combinations


def kao(amount, sums):
    coms = combinations(range(1, 10), amount)
    return [list(el) for el in coms if sum(list(el)) == sums]


print(kao(3, 9))
print(kao(3, 7))

panheng

def answer(k: int, n: int):
    res = []
    lst = [i for i in range(1, 10)]
    product = list(itertools.product(lst, repeat=k))  # 求笛卡尔积
    for comb in product:  # 筛选组合结果
        if sum(comb) == n and len(set(comb)) == k:
            if sorted(comb) not in res:  # 剔除排列结果
                res.append(list(comb))
    return res

zltzlt

kaohsing 发表于 2019-9-29 21:51

恭喜通过！

执行用时：44 ms

zltzlt

panheng 发表于 2019-9-29 21:52

输入 k = 8, n = 36 超出内存限制

panheng

zltzlt 发表于 2019-9-29 21:56
输入 k = 8, n = 36 超出内存限制

打个补丁，用combinations方法

def answer(k: int, n: int):
    res = []
    lst = [i for i in range(1, 10)]
    product = list(itertools.combinations(lst, k))
    for comb in product:
        if sum(comb) == n and len(set(comb)) == k:
            res.append(list(comb))
    return res

zltzlt

panheng 发表于 2019-9-29 22:10
打个补丁，用combinations方法

这样更省时

zltzlt

panheng 发表于 2019-9-29 22:10
打个补丁，用combinations方法

恭喜通过！

执行用时：48 ms

jdzzj

def combinationSum3(self, k: int, n: int) -> List[List[int]]:
    return [i for i in itertools.combinations(range(1,10),k) if sum(i)==n]

      

angtn

过来学习，顺便偷师

from itertools import combinations
x = lambda k,n : [i for i in combinations(range(1,10),k) if sum(i)==n]

x(3,7)
x(3,8)
x(3,9)

战场原

def solution(k: int, n: int):
    def findNsum(nums, target, N, result, results):
            if len(nums) < N or N < 2 or target < nums[0]*N or target > nums[-1]*N:  
                return
            if N == 2:
                l,r = 0,len(nums)-1
                while l < r:
                    s = nums[l] + nums[r]
                    if s == target:
                        results.append(result + [nums[l], nums[r]])
                        l += 1
                        while l < r and nums[l] == nums[l-1]:
                            l += 1
                    elif s < target:
                        l += 1
                    else:
                        r -= 1
            else:
                for i in range(len(nums)-N+1):
                    if i == 0 or (i > 0 and nums[i-1] != nums[i]):
                        findNsum(nums[i+1:], target-nums[i], N-1, result+[nums[i]], results)

    results = []
    findNsum([1,2,3,4,5,6,7,8,9], n, k, [], results)
    return results

jay_jiang

def fun(n,k):
        min=sum([10**x  for x in range(k) ])
        max=sum(9*10**x for x in range(k))
        h=[list(str(i)) for i in range(min,max+1) if n==sum([int(x) for x in list(str(i))]) and len(set(list(str(i))))==k]
        return h

阴阳神万物主

我写的长，因为没有去看官方文档，所以好多现成的工具函数不会用（之前见过也忘记了……）
效率上，我尽力了

def 求解(n, k, 当前=[], 初级=True, 结果 = []):#因为需要的最大递归深度为9 所以直接用递归
    if 初级:
        结果 = []
        if k <= 0:                            #不超过0个数的组合没法相加
            return []
        elif n <= 0:                          #正整数之和不可能是非整数
            return []
        for i in range(1,11-k):
            结果=求解(n, k-1, [i], False, 结果)
        return 结果
    else:
        for i in range(max(当前[:])+1,11-k):
            当前.append(i)
            和 = sum(当前)
            相差 = n-和
            #print('调试', 结果, 当前, k, 和, n, max(当前), (相差 <= max(当前)))
            if (相差) and (相差 <= max(当前)):
                if 相差 < 0:
                    return 结果
                #print('调试',当前.pop())
                当前.pop()
                continue
            if k > 1:
                if(n == 和):
                    return 结果
                #print('调试 取下一个数', 当前)
                结果=求解(n, k-1, 当前[:], False, 结果)
            elif ((k == 1)and(not 相差)):
                结果.append(当前)#[:])
                #print('调试 结果加', 当前)
                return 结果
            
            #print('调试', 当前.pop())
            当前.pop()
        return 结果

if __name__ == '__main__':
    print('例1 输出：',求解(7,3))
    print('例2 输出：',求解(9,3))
    print('自测 输出：',求解(1, 3))#不可能找出来的情况，我这里选择的是返回空列表

    

zltzlt

jdzzj 发表于 2019-9-29 22:35

恭喜通过！

执行用时：36 ms

zltzlt

angtn 发表于 2019-9-29 23:06
过来学习，顺便偷师

恭喜通过！

执行用时：40 ms

zltzlt

战场原 发表于 2019-9-29 23:19
def solution(k: int, n: int):
    def findNsum(nums, target, N, result, results):
            if l ...

恭喜通过！

执行用时：44 ms

zltzlt

jay_jiang 发表于 2019-9-29 23:26
def fun(n,k):
        min=sum([10**x  for x in range(k) ])
        max=sum(9*10**x for x in range(k))

解答错误

输入：k = 3, n = 7
输出：[[1,2,4],[1,4,2],[1,6,0],[2,0,5],[2,1,4],[2,4,1],[2,5,0],[3,0,4],[3,4,0],[4,0,3],[4,1,2],[4,2,1],[4,3,0],[5,0,2],[5,2,0],[6,0,1],[6,1,0]]
预期结果：[[1,2,4]]

zltzlt

阴阳神万物主 发表于 2019-9-30 01:31
我写的长，因为没有去看官方文档，所以好多现成的工具函数不会用（之前见过也忘记了……）
效率上，我尽力 ...

解答错误

输入：n = 3, k = 7
输出：[]
预期结果：[[1,2,4]]

永恒的蓝色梦想

def func(k,n):
        from itertools import combinations as comb
        return [list(i) for i in comb(range(1,10),k)if sum(i)==n]

阴阳神万物主

zltzlt 发表于 2019-9-30 18:18
解答错误

输入：n = 3, k = 7

内个，题目不是说

相加之和为 n 的 k 个数的组合

吗？
n = 3,k =7 时，意思不就是 7 个数的和要等于 3 吗？确实不存在啊……