Finding prefix sum
for ( int s = min_x ; s <= max_x ; s ++ ) { if ( ! weight_at_x . ContainsKey ( s ) ) { sum_till . Add ( sum_till [ sum_till . Count - 1 ] ) ; } else { sum_till . Add ( sum_till [ sum_till . Count - 1 ] + weight_at_x [ s ] ) ; } } int total_sum = sum_till [ sum_till . Count - 1 ] ; int partition_possible = 0 ; for ( int i = 1 ; i < sum_till . Count ; i ++ ) { if ( sum_till [ i ] == total_sum - sum_till [ i ] ) partition_possible = 1 ;