leetcode804

Logic:
Get the average of the array, then backtrack the subarray with the same average.
trick: be careful with sum * number % length; not only sum % length:
eg: 10 / 4 => 5/2, even sum % length !=0 , it still works!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class solution{
	public boolean splitArraySameAverage(int[] A){
	int len = A.length;
	if(len==1) return false;
	int s = 0;
	for(int i: A){
		s += i;
	}
	Arrays.sort(A);
	for(int i = 1; i <= len/2; i++){
		if((s * i % len == 0) & (backtracking(A, s * i /len, i, 0)) return true;
		return false;
		}
	}
	public boolean backtrack(int[] A, int target, int k, int start){
		if(k==0) return target==0;
		if(A[start] > target/k) return false;
		for(int i = start; i < A.length - k + 1; i++){
			if(i > start && A[i]==A[i-1]) continue;
			if(backtrack(A, target - A[i], k -1, i + 1)) return true;
		}
		return false;
	}
}