Given a integer array, and a number n. Return true if n can be consisted by a subset of array. For example, arr[]={3, 2, 3, 5}, n=11, return true; arr[]={3, 2, 3, 5}, n=12, return false

sumofSubset

/*
	 * the algorithm will generate sums for all possible subset of the array
	 * and put them into a hash, return true if the target is found in the hash
	 * the optimization here is to check hash contains the target during the update
	 */
	public static boolean sumOfSubSet(int[] nums, int target){
		Set<Integer> sums = new HashSet<Integer>();
		//start with empty set
		sums.add(0);
		if(sums.contains(target))
			return true;
		for(int num : nums){
			//make a copy of the sums we have so far
			Set<Integer> temp = new HashSet<Integer>(sums);		
			//for each previous sum preSum we add the current number num
			for(int preSum : sums){
				temp.add(preSum + num);
			}
			//swap 
			sums = temp;
			if(sums.contains(target))
				return true;
		}	
		return false;		
	}