小编use*_*417的帖子

我很乐意得到一些帮助.

我有以下问题:

我给出了一个数字列表seq和一个目标号码,我需要写两件事:

1. 递归解决方案,True如果存在等于目标编号的子序列的总和,则返回False.例:

   subset_sum([-1,1,5,4],0)   # True
   subset_sum([-1,1,5,4],-3)  # False
   

   Run Code Online (Sandbox Code Playgroud)

2. 其次,我需要使用我在之前的解决方案中编写的内容编写解决方案,但现在使用memoization,它使用一个字典,其中键是元组: (len(seq),target)

对于数字1,这是我到目前为止所得到的:

def subset_sum(seq, target):
    if target == 0: 
        return True
    if seq[0] == target:
        return True
    if len(seq) > 1:
        return subset_sum(seq[1:],target-seq[0]) or subset_sum(seq[1:],target)
    return False

不确定我是否正确,所以如果我能得到一些意见,我将不胜感激.

对于2号:

def subset_sum_mem(seq, target, mem=None ):
    if not mem:
        mem = {}
    key=(len(seq),target)
    if key not in mem:
        if target == 0 or seq[0]==target:
            mem[key] = True
        if len(seq)>1:
            mem[key] = subset_sum_mem(seq[1:],target-seq[0],mem) or subset_sum_mem(seq[1:],target,mem)
        mem[key] …

我需要k从长度列表中生成长度的所有组合n,我必须使用递归来完成.

例如:

INPUT:  choose_sets([1,2,3,4],3)
OUTPUT: [[1,2,3],[1,2,4],[1,3,4],[2,3,4]]

INPUT:  choose_sets([1,2,3,4],2)
OUTPUT: [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]

我在代码中执行此操作时遇到困难,所以我很乐意提供一些帮助.到目前为止这是我的代码(我遗漏的东西只是不知道是什么):

def choose_sets(lst,k):

    if k == len(lst):
        return lst
    if k == 0:
        return []
    if k > len(lst):
        return []

    sets=[]
    sub_lst=lst[:]
    sub_lst.remove(sub_lst[0])

    a= choose_sets(sub_lst,k-1)
    for i in a:
        i.append(lst[0])
    sets.append(a)

    b= choose_sets(sub_lst,k)
    sets.append(b)


    return sets