Dynamic Programming21 sections · 916 units
Open in Course

Challenge: Partition Reconstruction

Finding the actual subsets

The DP tells you if a partition exists, but not which elements to use. To reconstruct, track how each sum was achieved. Modify the DP: when dp[snums[i]]dp[s - nums[i]] is true and you set dp[s]=truedp[s] = true, record that element ii contributed to sum ss.

Or backtrack: start at target sum, for each element check if dp[targetnums[i]]dp[target - nums[i]] was true before adding element ii. If so, include it and continue. Try reconstructing the partition for [1,5,11,5][1, 5, 11, 5]. Which elements form the subset summing to 1111?