给一个正整数数组nums,再给一个正整数X,求数组中相加和等于X的子序列,子序列不要求连续,不要求顺序。请写java代码实现
时间: 2024-03-08 20:47:34 浏览: 49
leetcode卡-FirstMissingPositives:第一个缺失的正数
以下是Java实现代码:
```java
import java.util.ArrayList;
import java.util.List;
public class Solution {
public List<List<Integer>> findSubsequences(int[] nums, int target) {
int n = nums.length;
List<List<Integer>>[] dp = new List[target+1];
for (int i = 0; i <= target; i++) {
dp[i] = new ArrayList<>();
if (i == 0) {
dp[i].add(new ArrayList<>());
}
}
for (int i = 0; i < n; i++) {
for (int j = target; j >= nums[i]; j--) {
for (List<Integer> path : dp[j-nums[i]]) {
List<Integer> newPath = new ArrayList<>(path);
newPath.add(nums[i]);
dp[j].add(newPath);
}
}
}
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]中包含了所有相加和等于目标数的子序列。
阅读全文