“找到数组中和为target的组合(数字可重复)”问题描述如下: 给定一个数组nums=[2,3,5]和一个固定的值target=8。找出数组nums中所有可以使数字和java为target的组合(数字可重复)。 输出样例: {2,2,2,2} {3,5} {2,3,3}
时间: 2023-04-08 09:03:17 浏览: 90
可以回答这个问题。这是一个经典的回溯算法问题。我们可以使用递归函数来实现。具体实现方法是,从数组的第一个元素开始,依次枚举每个元素,如果当前元素小于等于目标值,就将其加入到当前组合中,并递归处理剩余的部分,直到目标值为0或者当前元素大于目标值为止。如果目标值为0,就将当前组合加入到结果集中。如果当前元素大于目标值,就直接返回。代码如下:
```
public List<List<Integer>> combinationSum(int[] nums, int target) {
List<List<Integer>> res = new ArrayList<>();
Arrays.sort(nums);
backtrack(nums, target, 0, new ArrayList<>(), res);
return res;
}
private void backtrack(int[] nums, int target, int start, List<Integer> path, List<List<Integer>> res) {
if (target == 0) {
res.add(new ArrayList<>(path));
return;
}
for (int i = start; i < nums.length; i++) {
if (nums[i] > target) {
break;
}
path.add(nums[i]);
backtrack(nums, target - nums[i], i, path, res);
path.remove(path.size() - 1);
}
}
```
对于输入样例,输出结果为:
```
[[2, 2, 2, 2], [2, 3, 3], [3, 5]]
```
阅读全文