Partition problem - finding elements of the set using minimal memory

Question

I have to solve a classic partition problem using dynamic programming. I have an array of positive integers as an input where n is the number of integers and s is the sum of those integers, and I need to find the minimum difference between two sets that can be constructed using elements from input. I also need to output an boolean array called "ownership" of the same size as input array, which provides information if the elements belong to the first or second optimal set. For example, if i-th value in the ownership array is true then the i-th element of the input array belongs to the first set.

My program finds minimum difference using bottom-up approach. The task requires that the memory complexity of the program is θ(s), so instead of using 2D array of size n*s like in classical approach, I'm using only two rows of that array. In the first row I keep the previous processed row, so I can fill the second row basing on the previous solutions.

The problem is that with this memory optimization I'm not sure how I should fill the ownership array.

I know that one could retrieve the set elements using backtracking in n*s array. However, because of the task constraints, I cannot use that method and I have no idea on how I could efficiently construct ownership table.

Is there a way to efficiently find which elements belong to which of those two optimal sets, with constraint of memory complexity θ(s) and time complexity O(n*s) in the bottom-up approach?

My current code in C#:

 public int SetsMinimum(int[] tab, out bool[] ownership)
 {
    int n = tab.Length;
    int sum = 0;
    foreach (int v in tab) sum += v;
    ownership = new bool[n];
    bool[,] dp = new bool[2, sum + 1];
    int min = sum;
    dp[0, 0] = true;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= sum; j++)
        {
            dp[1,j] = dp[0,j];
            if (j - tab[i - 1]>=0)
            {
                dp[1, j] = dp[0, j - tab[i - 1]];
            }     
        }
        for(int j=0;j<sum;j++)
        {
            if (dp[1, j])
            {
                int cMin = Math.Abs((sum - j) - j);
                if (min>cMin)
                {
                    min = cMin;
                }
            }    
            dp[0, j] = dp[1, j];
        }
    }
    return min;
}

Answer 1

I found a solution yesterday:

1. Initialize another array of sum+1 elements and fill it with zeroes.
2. When iterating over dp array, save in previous array index of first element which allowed to achieve every sum. For example, for {4,3,2} you could achieve sum 7 when you used second element, and you could get sum of 4 with the first element.
3. After getting minimum difference, pick one of the optimal sets sum, either (sum-min)/2, or sum-((sum-min)/2).
4. Jump to sum in index array, set the ownership array to true in the index pointed in index array, then substract the element from the sum. Repeat until your sum is zero.

This approach will only pick neccesary elements to construct either one of sets sum, and it will work in O(n*s) time since the index array can be filled during bottom-up approach.

Answer 2

You can write a function which runs in memory O(s) that runs DP once and finds out the closest target sum.

You can write a function which runs in memory O(s) that runs DP once and finds out whether the last value has to be true or false in the ownership array to reach that target sum.

Run the second function repeatedly to pick off each member of the ownership array from the end to the front.

This will take memory O(s) and time O(s * n^2). (Because you run n DPs.) As opposed to the usual DP approach that takes memory O(s * n) and time O(s * n).