Java递归问题

我在Java中有一个递归面试问题，需要你的帮助。

编写一个**Java function** ，使得::给定一个整数数组，是否可以将整数分成两组，这样两个组的总和是相同的，具有这些约束：所有的值都是5的倍数必须在一个组中，并且所有3的倍数（而不是5的倍数）必须在另一个中。 （不需要循环。）

split53({1,1}) → true
split53({1, 1, 1}) → false
split53({2, 4, 2}) → true

PS：这是hewlett packard的采访问题

Answer 1

问题可以很容易地简化为：给定一组整数和一个整数target ，是否有可能找到总和等于target的numbers子集？
如果过渡需要澄清，请告诉我。

它可以用DP在O(numbers.size * target)时间内求解。 这个想法如下

1. 当numbers.size为0 ，唯一可达的和为0 。
2. 假设我们有numbers == {1, 3} ，在这种情况下，总和{0, 1, 3, 4} 0,1,3,4 {0, 1, 3, 4}可用。 如果我们在numbers 4添加另一个元素怎么办？ 现在，仍然可以达到所有旧的和一些新的： {0 + 4, 1 + 4, 3 + 4, 4 + 4} 。 因此，对于numbers == {1, 3, 4} ，可用的总和是{0, 1, 3, 4, 5, 7, 8} 0,1,3,4,5,7,8 {0, 1, 3, 4, 5, 7, 8} 。
3. 以这种方式，按编号添加数字，您可以构建可达总和的列表。

一个工作示例（它不处理负数，但你可以很容易地解决它）

 boolean splittable(int[] numbers, int target) { boolean[] reached = new boolean[target + 1]; reached[0] = true; for (int number : numbers) { for (int sum = target - 1; sum >= 0; --sum) { if (reached[sum] && sum + number <= target) { reached[sum + number] = true; } } } return reached[target]; } 

运行

 System.out.println(splittable(new int[]{3, 1, 4}, 7)); // => true System.out.println(splittable(new int[]{3, 1, 4}, 6)); // => false 

编辑
我刚刚注意到要求的“递归”部分。 好吧，如果这是硬性要求，DP可以通过memoization重写为递归。 这将保留运行时复杂性。

编辑2
在团体。 在继续算法之前，必须将可被3或5整除的元素分配给各个组。 假设所有元素s总和为s ，可被3整除的元素之和为s3 ，可被5整除但不是3的元素之和为s5 。 在这种情况下，在您分配了这些“特殊”元素之后，您必须将其余部分拆分为一个组中s/2 - s3总和为s/2 - s3 ，而另一个组中s/2 - s3总和为s/2 - s5 。

Answer 2

非常慢，但工作解决方案：

 static boolean canSplit(int[] arr, int lvl, int sum1, int sum2) { if (arr.length == lvl) { if (sum1 == sum2) { return true; } else { return false; } } if (arr[lvl] % 5 == 0) { return canSplit(arr, lvl + 1, sum1 + arr[lvl], sum2); } else if (arr[lvl] % 3 == 0) { return canSplit(arr, lvl + 1, sum1, sum2 + arr[lvl]); } return canSplit(arr, lvl + 1, sum1 + arr[lvl], sum2) || canSplit(arr, lvl + 1, sum1, sum2 + arr[lvl]); } 

调用函数：

 canSplit(arr, 0, 0, 0); 

Answer 3

代码可能会让我解雇。 但是会起作用：D

完全递归，同样致命。

 public boolean split53(int[] nums) { return split_fn(0, nums, 0, 0, false, false); } public boolean split_fn(int start, int[] nums, int left, int right, boolean fiveLeft, boolean chosen) { if (start >= nums.length) { if (left == right) return true; return false; } if (nums[start] % 5 == 0) { if (!chosen) { return split_fn(start + 1, nums, left + nums[start], right, true, true) || split_fn(start + 1, nums, left, right + nums[start], false, true); } else { return split_fn(start + 1, nums, left + ((fiveLeft) ? nums[start] : 0), right + ((!fiveLeft) ? nums[start] : 0), fiveLeft, chosen); } } if (nums[start] % 3 == 0 && nums[start] % 5 != 0) { if (!chosen) { return split_fn(start + 1, nums, left + nums[start], right, false, true) || split_fn(start + 1, nums, left, right + nums[start], true, true); } else { return split_fn(start + 1, nums, left + ((!fiveLeft) ? nums[start] : 0), right + ((fiveLeft) ? nums[start] : 0), fiveLeft, chosen); } } //standard case return split_fn(start + 1, nums, left + nums[start], right, fiveLeft, chosen) || split_fn(start + 1, nums, left, right + nums[start], fiveLeft, chosen); } 

Answer 4

这是真正的递归解决方案。

 private boolean split2(int index, int[] nums, int sum1, int sum2) { if (index >= nums.length) { return sum1 == sum2; } if (split2(index + 1, nums, sum1 + nums[index], sum2)) { return true; } if (split2(index + 1, nums, sum1, sum2 + nums[index])) { return true; } return false; } 

此代码将每个元素放入组中。 如果在任何组合中两个组相等，则返回true。 没有使用循环，只有一个函数。

最适合所有人

编辑：您的函数需要4个参数作为输入，而问题只作为数组输入。 你必须指定使用你的调用split2(0,nums,0,0);完成所需的functionsplit2(0,nums,0,0);

Answer 5

我不知道以下解决方案有多快或多慢。 但恰恰是它是一个递归回溯解决方案，它没有使用问题中提到的循环。

这是代码片段：

 public boolean split53(int[] nums) { int start = 0, firstPart = 0, secondPart = 0; if (split(start, nums, firstPart, secondPart)) { return true; } return false; } public boolean split(int start, int[] nums, int firstPart, int secondPart) { if (start >= nums.length) { return (firstPart == secondPart); } if ((start + 1) < nums.length && (nums[start] % 3 != 0) && (nums[start + 1] % 5 != 0) && split(start + 2, nums, firstPart + nums[start], secondPart + nums[start + 1])) { return true; } if ((start + 1) < nums.length && (nums[start + 1] % 3 != 0) && (nums[start] % 5 != 0) && split(start + 2, nums, firstPart + nums[start + 1], secondPart + nums[start])) { return true; } if ((nums[start] % 3 != 0) && split(start + 1, nums, firstPart + nums[start], secondPart)) { return true; } if ((nums[start] % 5 != 0) && split(start + 1, nums, firstPart, secondPart + nums[start])) { return true; } return false; } 

希望能帮助到你。