N SUM 数组中随便数相加的结果等于剩下的数相加和

N SUM 数组中任意数相加的结果等于剩下的数相加和

数组中任意数相加的和等于剩下的数相加的和：

比如{1,2,3}   1+2=3,所以是满足条件的。

仔细分析下这样的数组其实首先要满足一下几个条件：

1.数组整个数相加要是偶数。(a+b+c+*+****=2d)

2.数组中的最大数不能超过整个数组和的1/2，因为最大数肯定也在某一边，超过1/2的话，不成立。（不存在负数的情况下）

 

java代码如下 

/**
 * 
 */
package com.cxm;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * @author admin
 *
 */
public class NSum
{
	private static int[] array={1,1,2,3,1,2,2,2,2,1,1,1,1}; 
	
	public static boolean isNSumNum(){
		int sum =0 ;
		int k = array.length;
		for(int i = 0;i<k;i++){
			sum+=array[i];
		}
		//如果数组的总和不是偶数，这个数组肯定不满足条件
		if((sum&1)==1){
			return false;
		}
		int middle = sum>>1;
		Arrays.sort(array);
		int larget = array[k-1];
		
		//最大值肯定在一组中，如果最大值比均值大，这个数组肯定不满足条件
		if(larget>middle){
			return false;
		}
		if(larget==middle){
			return true;
		}
		
		int newTarget = middle-larget;
		
		for(int i =0;i<array.length&&array[i]<=newTarget;i++){
			if(array[i]==newTarget){
				return true;
			}
		}
		
		return threeSum(newTarget,-1);
	}
	
	public static boolean threeSum(int target,int z){
		for(int i = z+1 ;i<array.length&&array[i]<=target;i++){
			if(twoSum1(target-array[i],i)){
				return true;
			}else{
				return threeSum(target-array[i],i);
			}
		}
		return false;
	}
	
	/**
	 * 两个数相加的目标位target
	 * @param target
	 */
	public static boolean twoSum1(int target,int z){
		Map<Integer,Integer> map = new HashMap<Integer,Integer>();
		for(int i =z+1;i<array.length&&array[i]<=target;i++){
			if(!map.containsKey(array[i])){
				map.put(target-array[i], i);
			}
			if(map.containsKey(array[i])){
				int k = map.get(array[i]);
				if(i!=k&&z!=i&&k!=z){
					return true;
				}
			}
		}
		return false;
	}
	
	public static void main(String[] args)
	{
		System.out.println(isNSumNum());
	}
}