给一个正整数数组nums,再给一个正整数X,求数组中相加和等于X的子序列,子序列不要求连续,不要求顺序。请用回溯法写java代码实现
时间: 2024-03-08 12:47:35 浏览: 63
java 数组求和计算
4星 · 用户满意度95%
以下是Java实现代码:
```java
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class Solution {
public List<List<Integer>> findSubsequences(int[] nums, int target) {
Arrays.sort(nums);
List<List<Integer>> res = new ArrayList<>();
dfs(nums, target, 0, new ArrayList<>(), 0, res);
return res;
}
private void dfs(int[] nums, int target, int start, List<Integer> path, int curSum, List<List<Integer>> res) {
if (curSum == target && path.size() > 0) {
res.add(new ArrayList<>(path));
return;
}
if (curSum > target) {
return;
}
for (int i = start; i < nums.length; i++) {
if (i > start && nums[i] == nums[i-1]) {
continue;
}
path.add(nums[i]);
dfs(nums, target, i+1, path, curSum+nums[i], res);
path.remove(path.size()-1);
}
}
}
```
该算法使用回溯法,首先对原数组进行排序,然后从第一个数开始遍历,每次将当前数加入路径中,并将其后面的数作为下一层的候选数,递归搜索,直到找到相加和等于目标数的路径,或者已经遍历完所有的数。为了避免重复,我们在递归时跳过相同的数。最后返回所有满足条件的路径。
阅读全文