PC
BAN USERHow does solving the problem in 1D lead to solution in 2D? Consider three groups with equal number of people, forming a triangle, the solution is the Fermat point, which is clearly inside the triangle. How to find that point based on the x and y picked individually?
 PC September 18, 2013We can sort the array from smallest to largest, then for each element i, we are looking for a subset in the range [0, i) with sum equals to arr[i], which is the subset sum problem and it is NPcomplete.
However, we can generate solutions with DP:
Solution(sum, i) = Solution(sum, i1)  Solution(sumarr[i], i1)
The DP algorithm can be implemented bottomup, and it's basically enumerating all possible combinations.
void increase_by(int nums[], int size, int inc) {
if (size == 0) { return; }
int sum = nums[size1] + inc;
int val = sum % 10;
int carry = (sum  val) / 10;
if (size > 1) {
increase_by(nums, size  1, carry);
} else {
cout << carry;
}
cout << ' ' << val; // Suppose we are just printing to the console
}
void increase_by_one(int nums[], int size) {
increase_by(nums, size, 1);
}

PC
September 14, 2013 void print_subarray(int* data, int start, int end) {
for (int i = start; i <= end; i++) {
cout << data[i];
if (i < end) { cout << ", "; }
}
cout << endl;
return;
}
void find_subarray_partial(int* data, int* buffer, int* indexes, int start, int end) {
if (start > end) { return; }
if (start == end) {
if (data[start] == 0) {
print_subarray(data, start, start);
}
return;
}
int middle = start + (end  start) / 2;
find_subarray_partial(data, start, middle  1);
find_subarray_partial(data, middle + 1, end);
// Sub problem in which data[middle] must be part of the subarray
// 1. Calculate the sum around data[middle]
buffer[middle] = data[middle];
int sum = data[middle];
for (int i = middle  1; i >= start; i) {
sum += data[i];
buffer[i] = sum;
}
sum = data[middle];
for (int i = middle + 1; i <= end; i++) {
sum += data[i];
buffer[i] = sum;
}
// 2. Sort the sums on left and right side of data[middle] separately, and record indexes before sort. Insertion sort used here for simplicity but real implementation should be replaced by a sorting algorithm with complexity O(nlogn)
for (int i = start; i <= end; i++) {
indexes[i] = i;
}
for (int i = start; i < middle; i++) {
for (int j = start; j < i; j++) {
if (buffer[i] < buffer[j]) {
swap(buffer[i], buffer[j]);
swap(indexes[i], index[j]);
}
}
}
for (int i = middle + 1; i <= end; i++) {
for (int j = middle + 1; j < i; j++) {
if (buffer[i] < buffer[j]) {
swap(buffer[i], buffer[j]);
swap(indexes[i], index[j]);
}
}
}
// 3. Get pairs from left and right side of middle whose sums add up to data[middle]
int left = start;
int right = end;
int target = data[middle];
while (left < middle && right > middle) {
int sum = buffer[left] + buffer[right];
if (sum == target) {
// Found a pair, output the sequence
print_subarray(data, indexes[left], indexes[right]);
left++;
right++;
} else if (sum < target) {
left++;
} else {
right;
}
}
}
void find_subarray(int* data, int* indexes, int size) {
int* buffer = new int[size];
int* indexes = new int[size];
find_subarray_partial(data, buffer, 0, size  1);
delete [] buffer;
delete [] indexes;
}

PC
August 13, 2013 If the problem is looking for subarrays, then it can be solved by divide and conquer;
Split the problem into three subproblems:
1. All subarrays in array A[0...n/2  1] that sum to 0
2. All subarrays containing element a[n/2] that sum to 0
3. All subarrays in array A[n/2 + 1..n] that sum to 0
The time complexity is O(n (logn)^2)
T(n) = 2T(n/2) + nlogn
Space complexity is O(n)
Otherwise it is subset sum problem.
There should be one modification, if the next character is the same as the last character in the merged result, and the last character is chosen from a different string, the next character can be skipped.
 PC January 02, 2014