当前位置: 首页 > 知识库问答 >
问题:

打印数组的所有子集,其和等于目标和

龙逸清
2023-03-14

给定一个由N个元素组成的数组,找出数组的所有子集,其和等于目标值。
我已经看到了所有关于子集和的老问题,但没有一个对我有用。

  • 输入的第一行包含数组的整数N大小
  • 第二行包含由空格分隔的数组元素
  • 目标和值
  • 打印所有子数组(元素索引)。

我的代码对于小的输入工作得很好,但是对于N>150则需要很长的时间。有没有其他有效的算法可以做到这一点。请告诉我如何优化此代码以适应较大的输入。
这是我的代码

from collections import deque

class Pair:
    def __init__(self, i, j, path_set):
        self.i = i
        self.j = j
        self.path_set = path_set

def get_subsets(arr, n, value): 
    """
    This function appends all the possible paths in result list for the given target sum
    Arguments:
        arr = A list of numbers
        n = number of elements in that list arr
        value = Target sum for which we want to generate table
    """
    # return immediately if there is no possible subset in arr whose sum is equal to value
    if dp[n][value] == False:
        return
        
    queue = deque()
    queue.append(Pair(n, value, set()))

    while len(queue) > 0:
        pair = queue.popleft()
        if pair.i == 0 or pair.j == 0:
            result.append(pair.path_set)
        else:
            exclude = dp[pair.i - 1][pair.j]
            if exclude:
                queue.append(Pair(pair.i-1, pair.j, pair.path_set))

            if pair.j >= arr[pair.i-1]:
                include = dp[pair.i - 1][pair.j - arr[pair.i -1]]
                if include:
                    b = pair.path_set.copy()
                    b.add(pair.i - 1)
                    queue.append(Pair(pair.i - 1, pair.j-arr[pair.i-1], b))
            

def make_dp(arr, n, value):
    """
    This function makes a table of target sum equal to the value
    Arguments:
        arr = A list of numbers
        n = number of elements in that list arr
        value = Target sum for which we want to generate table
    Returns:
        dp = A 2D boolean table
    """
    dp = [[False for i in range(value+1)] for j in range(n+1)]
    
    for i in range(n+1):
        for j in range(value+1):
            if j ==0:
                dp[i][j] = True
            elif i == 0:
                dp[i][j] = False
            else:
                if dp[i-1][j]:
                    dp[i][j] = True
                elif j >=arr[i-1]:
                    if dp[i-1][j-arr[i-1]]:
                        dp[i][j] = True
    return dp

if __name__ == '__main__':
    n = int(input())
    arr = list(map(int, input().split()))
    value = int(input())
    dp = make_dp(arr, n, value)
    result = []
    get_subsets(arr, n, value)
    print(result)

需要花费大量时间的输入:

200
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200
200

请优化此代码或告诉我任何其他方法做同样的。提前道谢。

共有1个答案

廖臻
2023-03-14

您可能会发现使用迭代工具和组合更有效率一点。代码也简单得多。

from itertools import chain, combinations

li = [1,2,3,4,5,6]
s=12

itr=chain.from_iterable(combinations(li, n) for n in range(len(li)+1))

result = [el for el in itr if sum(el)==s]

print(result)

输出:

[(1, 5, 6), (2, 4, 6), (3, 4, 5), (1, 2, 3, 6), (1, 2, 4, 5)]
 类似资料:
  • 我一直在学习动态规划,我想通过打印出所有相加为一个数字的子集来进一步研究经典的子集和问题。我该怎么做呢?到目前为止,我知道如何根据是否存在相加的子集来打印true或false 如果可能,我想返回所有子集的数组。

  • 我正在练习一些动态规划问题,并试图解决用给定的和打印所有子集的问题。例如:对于和,我应该得到以下结果: 我在不使用表的情况下得到了所需的结果,我使用表来防止重复调用相同的表和求和。但是,当使用表时,我在输出中没有得到。 请帮忙!

  • 我正在进行JavaScript会话。在我的编码练习中找到此代码。我理解逻辑,但我没有得到这个map[nums[x]]条件。 我试图从一个指定的数组中获取元素对,该数组的和等于一个特定的目标数。我已经写了下面的代码。 有没有比上述两种解决方案更优化的方法?有人能解释第一种解决方案吗?这个条件到底指的是什么映射[nums[x]]?

  • 如果有一个包含一组正数和负数的数组,请打印所有等于0的子集和。 我可以想出一种方法,在那里我可以制作givcen阵列的所有功率集,并检查它们的总和是否为0。但对我来说,这不像是优化的解决方案。 看完网上看起来有点类似的问题,好像可以用下面的程序动态编程来解决,看看是否有组合存在,让和11只是一个例子? 但是我不知道如何将上述程序扩展到 1)包括负数 2)找到使和为零的元素组合(上面的程序只是发现它

  • 如何加快以下问题陈述的执行速度?我有一个正确的解决方案,通过每一个测试的小输入。但是,它超过了较大输入的时间限制。我当前的实现是数组大小的二次型。 你的答案应该是基于1的,这意味着数组的第一个位置是1而不是0。 实施

  • 我的问题是,我需要从这个布尔数组中提取和等于指定和的实际子集。我尝试过这样做,但是我的方法中的逻辑(涉及到使用布尔数组来减少我必须分析的子集的数量)变得相当复杂,并且我很难实现它。 有没有人知道当使用生成的布尔数组时,找到其和等于给定和的所有子集的好方法? 编辑%1 输入 输出