有一个由数字组成的数组,给定一个数字,罗列所有累加之和等于这个数字的答案,请详细写出算法的代码
时间: 2023-03-15 07:56:10 浏览: 78
这是一个典型的背包问题,可以使用动态规划的方法来解决。算法代码如下://定义数组和给定数字
int[] nums = {0,1,2,3,4,5,6,7,8,9};
int target = 8;
//定义二维数组(nums.length+1)x(target+1)
boolean[][] dp = new boolean[nums.length+1][target+1];//初始化状态(每种状态的初始值)
//当target为0时,表示没有数字累加之和可以等于0,因此dp[i][0]为false
//当nums数组只有一个元素时,只有当nums[0]等于target时,dp[1][target]才为true
for (int i = 0; i <= nums.length; i++) {
dp[i][0] = false;
}
for (int j = 0; j <= target; j++) {
if (j == nums[0]) {
dp[1][j] = true;
}
}//动态规划
for (int i = 2; i <= nums.length; i++) {
for (int j = 1; j <= target; j++) {
if (j < nums[i-1]) {
dp[i][j] = dp[i-1][j];
} else {
dp[i][j] = dp[i-1][j] || dp[i-1][j-nums[i-1]];
}
}
}//查找累加之和等于target的所有答案
List<List<Integer>> ans = new ArrayList<>();
if (dp[nums.length][target]) {
List<Integer> tmp = new ArrayList<>();
int i = nums.length;
int j = target;
while (i > 0 && j > 0) {
if (dp[i][j] && dp[i-1][j]) {
i--;
} else {
tmp.add(nums[i-1]);
j -= nums[i-1];
i--;
}
}
ans.add(tmp);
}//输出答案
for (List<Integer> list : ans) {
System.out.println(list);
}