Java找到数组中和为target的组合(数字可重复)”问题描述如下: 给定一个数组nums=[2,3,5]和一个固定的值target=8。找出数组nums中所有可以使数字和为target的组合(数字可重复)
时间: 2023-04-09 14:00:50 浏览: 136
从一组数中找出和为某数的所有组合
5星 · 资源好评率100%
可以使用回溯算法来解决这个问题。具体步骤如下:
1. 定义一个函数backtrack来进行回溯,该函数有三个参数:当前组合的和curSum、当前组合的元素下标startIndex、当前组合的列表combination。
2. 在backtrack函数中,如果当前组合的和等于target,则将当前组合加入结果列表中。
3. 否则,从startIndex开始遍历数组nums,将当前元素加入组合中,并递归调用backtrack函数,同时更新当前组合的和和元素下标。
4. 递归调用结束后,将当前元素从组合中删除,继续遍历数组nums中的下一个元素。
代码如下:
```
class Solution {
public List<List<Integer>> combinationSum(int[] nums, int target) {
List<List<Integer>> res = new ArrayList<>();
backtrack(nums, target, 0, new ArrayList<>(), res);
return res;
}
private void backtrack(int[] nums, int target, int startIndex, List<Integer> combination, List<List<Integer>> res) {
int curSum = 0;
for (int num : combination) {
curSum += num;
}
if (curSum == target) {
res.add(new ArrayList<>(combination));
return;
}
for (int i = startIndex; i < nums.length; i++) {
if (curSum + nums[i] <= target) {
combination.add(nums[i]);
backtrack(nums, target, i, combination, res);
combination.remove(combination.size() - 1);
}
}
}
}
```
阅读全文