给定一个数组nums=[2,3,5]和一个固定的值target=8。用Java找出数组nums中所有可以使数字和为target的组合(数字可重复)。
时间: 2023-04-02 12:05:05 浏览: 85
从一组数中找出和为某数的所有组合
5星 · 资源好评率100%
可以使用回溯算法来解决这个问题。具体步骤如下:
1. 定义一个List<List<Integer>>类型的变量res,用于存储所有符合条件的组合。
2. 定义一个List<Integer>类型的变量path,用于存储当前的组合。
3. 编写一个回溯函数backtrack,函数参数为当前的组合path和当前的和sum。
4. 在回溯函数中,首先判断当前的和sum是否等于目标值target,如果是,则将当前的组合path加入到res中。
5. 然后遍历数组nums,对于每个数字num,如果当前的和sum加上num小于等于target,则将num加入到当前的组合path中,并递归调用backtrack函数,传入更新后的组合path和和sum+num。
6. 在递归调用结束后,需要将最后一个加入到组合path中的数字移除,以便进行下一次遍历。
7. 最后,调用backtrack函数,传入空的组合path和初始和,得到所有符合条件的组合。
Java代码如下:
class Solution {
public List<List<Integer>> combinationSum(int[] nums, int target) {
List<List<Integer>> res = new ArrayList<>();
List<Integer> path = new ArrayList<>();
backtrack(nums, target, res, path, );
return res;
}
private void backtrack(int[] nums, int target, List<List<Integer>> res, List<Integer> path, int sum) {
if (sum == target) {
res.add(new ArrayList<>(path));
return;
}
for (int i = ; i < nums.length; i++) {
if (sum + nums[i] <= target) {
path.add(nums[i]);
backtrack(nums, target, res, path, sum + nums[i]);
path.remove(path.size() - 1);
}
}
}
}
阅读全文