找到数组中和为target的组合(数字可重复)”问题描述如下: 给定一个数组nums=[2,3,5]和一个固定的值target=8。找出数组nums中所有可以使数字和为target的组合(数字可重复)。 输出样例: {2,2,2,2} {3,5} {2,3,3} ...... 请用Java语言编程实现上述问题。
时间: 2023-04-08 22:03:10 浏览: 114
好的,这是一个算法问题,我可以回答。这个问题可以使用回溯算法来解决。具体实现如下:
```
import java.util.ArrayList;
import java.util.List;
public 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> temp, int[] nums, int target, int start) {
if (target < 0) {
return;
}
if (target == 0) {
res.add(new ArrayList<>(temp));
return;
}
for (int i = start; i < nums.length; i++) {
temp.add(nums[i]);
backtrack(res, temp, nums, target - nums[i], i);
temp.remove(temp.size() - 1);
}
}
}
```
这个算法的时间复杂度是O(N^target),其中N是数组nums的长度。
阅读全文