leetcode416.分割等和子集回溯java提示： 1 <= nums.length <= 200 1 <= nums[i] <= 100

题目描述：

给定一个只包含正整数的非空数组，是否可以将这个数组分成两个子集，使得两个子集的元素和相等。

示例：

输入：[1, 5, 11, 5]

输出：true

解释：数组可以分割成 [1, 5, 5] 和 [11]。

解题思路：

这是一道经典的 0-1 背包问题，可以使用动态规划或者回溯算法解决。

使用回溯算法，需要定义一个 backtrack 函数，该函数有三个参数：

- 数组 nums；
- 当前处理到的数组下标 index；
- 当前已经选择的元素和 leftSum。

回溯过程中，如果 leftSum 等于数组元素和的一半，那么就可以直接返回 true。如果 leftSum 大于数组元素和的一半，那么就可以直接返回 false。如果 index 到达数组末尾，那么就可以直接返回 false。

否则，就对于当前元素，有选择和不选择两种情况。如果选择当前元素，那么 leftSum 就加上当前元素的值，index 就加 1。如果不选择当前元素，那么 leftSum 不变，index 也加 1。最终返回所有可能性的结果中是否有 true。

Java 代码实现：

class Solution {
public boolean canPartition(int[] nums) {
int sum = 0;
for (int num : nums) {
sum += num;
}
if (sum % 2 != 0) {
return false;
}
Arrays.sort(nums);
return backtrack(nums, nums.length - 1, sum / 2);
}

private boolean backtrack(int[] nums, int index, int leftSum) {
if (leftSum == 0) {
return true;
}
if (leftSum < 0 || index < 0 || leftSum < nums[index]) {
return false;
}
return backtrack(nums, index - 1, leftSum - nums[index]) || backtrack(nums, index - 1, leftSum);
}
}