给一个正整数数组nums，再给一个正整数X，求数组中相加和等于X的子序列，子序列不要求连续，不要求顺序。请用动态规划实现

以下是Python实现代码：

def find_subsequences(nums, target):
    n = len(nums)
    dp = [[] for _ in range(target+1)]
    dp[0].append([])

    for i in range(n):
        for j in range(target, nums[i]-1, -1):
            for path in dp[j-nums[i]]:
                dp[j].append(path+[nums[i]])

    return dp[target]

该算法使用动态规划，我们定义一个二维数组dp，其中dp[i]表示相加和为i的所有子序列。初始时，dp[0]只包含一个空序列。然后我们从左到右遍历数组nums，对于每个数nums[i]，我们从右到左遍历dp数组，对于dp[j]，如果j >= nums[i]，则将dp[j-nums[i]]中的所有子序列添加上nums[i]，得到新的子序列，并将其加入到dp[j]中。最终，dp[target]中包含了所有相加和等于目标数的子序列。

相关问题

给一个正整数数组nums，再给一个正整数X，求数组中相加和等于X的子序列，子序列不要求连续，不要求顺序。请写代码实现

以下是Python实现代码：

def find_subsequences(nums, target):
    def dfs(start, path, cur_sum):
        if cur_sum == target:
            res.append(path)
            return
        if cur_sum > target:
            return
        for i in range(start, len(nums)):
            if i > start and nums[i] == nums[i-1]:
                continue
            dfs(i+1, path+[nums[i]], cur_sum+nums[i])

    nums.sort()
    res = []
    dfs(0, [], 0)
    return res

该算法使用回溯法，首先对原数组进行排序，然后从第一个数开始遍历，每次将当前数加入路径中，并将其后面的数作为下一层的候选数，递归搜索，直到找到相加和等于目标数的路径，或者已经遍历完所有的数。为了避免重复，我们在递归时跳过相同的数。最后返回所有满足条件的路径。

给你 nums ，它是一个大小为 2 * n 的正整数数组。你必须对这个数组执行 n 次操作。 在第 i 次操作时（操作编号从 1 开始），你需要： 选择两个元素 x 和 y 。 获得分数 i * gcd(x, y) 。 将 x 和 y 从 nums 中删除。 请你返回 n 次操作后你能获得的分数和最大为多少。 函数 gcd(x, y) 是 x 和 y 的最大公约数。

您可以使用贪心算法来解决此问题。

在每次操作中，您都应该尽可能选择两个元素 x 和 y，使得它们的最大公约数尽可能大。因为这样能使得获得的分数尽可能多。

为了使最大公约数尽可能大，您应该优先选择两个数字中较小的数字。因为如果两个数字都较小，那么它们的最大公约数就会更大。

因此，在每次操作中，您应该优先选择数组 nums 中最小的两个数字。然后按照从 1 到 n 的顺序依次计算每次操作获得的分数，并将它们相加。这样就可以得到最终的答案。

例如，假设 nums 是 [8, 12, 4, 10]，那么您应该这样进行操作：

- 第一次操作：选择 4 和 8，得分为 1 * gcd(4, 8) = 1 * 4 = 4。删除 4 和 8 后，数组变为 [12, 10]。
- 第二次操作：选择 10 和 12，得分为 2 * gcd(10, 12) = 2 * 2 = 4。删除 10 和 12 后，数组为空。

总分数为 4 + 4 = 8。

请注意，在这种情况下，如果您选择的顺序不同，最终得分也可能不同。例如，如果您先选择 12 和 10