中级农民
- 积分
- 113
- 大米
- 颗
- 鳄梨
- 个
- 水井
- 尺
- 蓝莓
- 颗
- 萝卜
- 根
- 小米
- 粒
- 学分
- 个
- 注册时间
- 2012-4-1
- 最后登录
- 1970-1-1
|
- import java.util.*;
- public class PartitionMinDifferenceSubsetSum {
- public static void main(String[] args) {
- int[] input1 = {1, 5, 5, 11};
- System.out.println("1, 5, 5, 11 : " + minDifference(input1));
- int[] input2 = {3, 1, 4, 2, 2, 1};
- System.out.println("3, 1, 4, 2, 2, 1 : " + minDifference(input2));
- }
- private static int minDifference(int[] nums) {
- if (nums == null || nums.length == 0) {
- return 0;
- }
- int sum = 0;
- for (int num : nums) {
- sum += num;
- }
- return minDifference(nums, 0, 0, sum);
- }
- private static int minDifference(int[] nums, int index, int curSum, int sum) {
- if (index == nums.length) {
- return Math.abs(curSum - (sum - curSum));
- }
- return Math.min(minDifference(nums, index + 1, curSum, sum),
- minDifference(nums, index + 1, curSum + nums[index], sum));
- }
- }
复制代码 |
|