Java找到数组中和为target的组合(数字可重复)”问题描述如下: 给定一个数组nums=[2,3,5]和一个固定的值target=8。找出数组nums中所有可以使数字和为target的组合(数字可重复)
时间: 2023-04-09 11:00:46 浏览: 89
可以使用回溯算法来解决这个问题。具体步骤如下:
1. 定义一个函数backtrack来进行回溯,该函数接收三个参数:当前的组合combination,当前的和sum,以及当前的位置start。
2. 在backtrack函数中,首先判断当前的和是否等于target,如果是,则将当前的组合加入结果集中。
3. 然后从start位置开始遍历数组,对于每个数字,将其加入组合中,并递归调用backtrack函数,同时更新当前的和。
4. 递归调用结束后,将组合中最后一个数字移除,同时更新当前的和。
5. 最后返回结果集。
具体实现如下:
```
class Solution {
public List<List<Integer>> combinationSum(int[] nums, int target) {
List<List<Integer>> res = new ArrayList<>();
backtrack(res, new ArrayList<>(), nums, target, 0);
return res;
}
private void backtrack(List<List<Integer>> res, List<Integer> combination, int[] nums, int target, int start) {
int sum = 0;
for (int num : combination) {
sum += num;
}
if (sum == target) {
res.add(new ArrayList<>(combination));
return;
}
for (int i = start; i < nums.length; i++) {
combination.add(nums[i]);
backtrack(res, combination, nums, target, i);
combination.remove(combination.size() - 1);
}
}
}
```
注意,这里的回溯算法并不是最优解,时间复杂度为O(N^target),可以使用动态规划来优化。
阅读全文