原创
数组定和问题：数组中和为target的元素组合
返回结果
// 返回结果
private static List<List<Integer>> ans = new ArrayList<>();
// 临时结果
private static List<Integer> temp = new ArrayList<>();
数组中的元素可以取任意多次（后面的元素能出现在前面）
例如：[1, 1, 1], [1, 2], [2, 1]
public static void helper(int[] nums, int target) {
// 终止条件
if (target < 0) {
return;
}
if (target == 0) {
ans.add(new ArrayList<>(temp));
return;
}
// 迭代
for (int i = 0; i < nums.length; i++) {
temp.add(nums[i]);
// 递归
helper(nums, target - nums[i]);
temp.remove(temp.size() - 1);
}
}
数组中的元素可以取任意多次（后面的元素不能出现在前面）
例如：[1, 1, 1], [1, 2]
public static void helper(int[] nums, int target, int start) {
// 终止条件
if (target < 0) {
return;
}
if (target == 0) {
ans.add(new ArrayList<>(temp));
return;
}
// 迭代
for (int i = start; i < nums.length; i++) {
temp.add(nums[i]);
// 递归
helper(nums, target - nums[i], i);
temp.remove(temp.size() - 1);
}
}
数组中的元素只能取一次
例如：[1, 2]
public static void helper(int[] nums, int target, int start) {
// 终止条件
if (target < 0) {
return;
}
if (target == 0) {
ans.add(new ArrayList<>(temp));
return;
}
// 迭代
for (int i = start; i < nums.length; i++) {
temp.add(nums[i]);
// 递归
helper(nums, target - nums[i], i + 1);
temp.remove(temp.size() - 1);
}
}
可替代的终止方案（终止条件）
public static void helper(int[] nums, int target, int start) {
// 第一种终止方案
// if (target < 0) {
// return;
// }
if (target == 0) {
ans.add(new ArrayList<>(temp));
return;
}
// 迭代
for (int i = start; i < nums.length; i++) {
// 第二种终止方案
if (nums[i] <= target) {
temp.add(nums[i]);
// 递归
helper(nums, target - nums[i], i + 1);
temp.remove(temp.size() - 1);
}
}
}
数组中的元素可以取有限次
此处nums数组指定每个元素最多可以使用的次数，value数组等同上文nums数组
public static void helper(int[] value, int[] nums, int target, int start) {
// 判断边界
if (target == 0) {
ans.add(new ArrayList<>(temp));
return;
}
// 尝试所有可能
for (int i = start; i < value.length; i++) {
// 终止条件
if (nums[i] > 0 && nums[i] <= target) {
temp.add(value[i]);
nums[i]--;
helper(value, nums, target - value[i], i);
temp.remove(temp.size() - 1);
nums[i]++;
}
}
}
——————————————分割线——————————————
数组定和问题，结果如果是全排列（限定元素只能取一次）呢？
public static void helper(int[] nums, int target, int[] visit) {
if (target == 0) {
ans.add(new ArrayList<>(temp));
return;
}
for (int i = 0; i < nums.length; i++) {
// visit的数组的判断可以让后面的元素出现在前面
if (visit[i] == 0) {
temp.add(nums[i]);
visit[i] = 1;
helper(nums, target - nums[i], visit);
temp.remove(temp.size() - 1);
visit[i] = 0;
}
}
}
测试案例
“数组中的元素可以取有限次” 不使用该案例
int[] nums = new int[]{1, 2};
int target = 3;