分割等和子集及路径_分割等和子集输出路径-CSDN博客

本文链接：https://blog.csdn.net/li_qw_er/article/details/124231008

该博客详细介绍了如何解决LeetCode中的416题，即分割等和子集的问题。博主提供了一个C++解决方案，通过动态规划和路径回溯的方法，在找到可行分割时输出一个集合的元素。代码中使用unordered_set存储集合的下标，以区分两个子集。博客还展示了几个示例输入和输出，验证了算法的正确性。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

leetcode 416. 分割等和子集的进阶题目
要求：当可以分割的时候，输出其中一个集合的元素

输出两个也是可以的

在输出的时候使用unordered_set存储集合的下标
那么此时在 unordered_set 中的下标为其中一个集合不在的为另一个集合

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int n = nums.size();
        if (n < 2) {
            return false;
        }
        int sum = 0, maxnum = 0;
        for (int i = 0; i < n; i++) {
            sum += nums[i];
            maxnum = max(maxnum, nums[i]);
        }
        if (sum & 1) {
            return false;
        }
        int target = sum / 2;
        if (target < maxnum) {
            return false;
        }
        vector<vector<int>> dp(n + 1, vector<int>(target + 1, 0));
        vector<vector<int>> path(n + 1, vector<int>(target + 1, 0));
        for (int i = 0; i <= n; i++) {
            dp[i][0] = 1;
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= target; j++) {
                int num = nums[i - 1];
                dp[i][j] = dp[i - 1][j];
                if (j >= num && !dp[i][j]) {
                    dp[i][j] = dp[i - 1][j - num];
                    if (dp[i][j]) {
                        path[i][j] = 1;
                    }
                }
            }
        }

        if (!dp[n][target]) {
            return false;
        }

        int i = n, j = target;
        while (i > 0 && j > 0) {
            if (path[i][j]) {
                cout << nums[i - 1] << " ";
                j -= nums[i - 1];
            }
            i--;
        }
        cout << endl;
        return true;
    }
};

int main()
{
    Solution solution = Solution();
    vector<int> nums = { 1,5,11,5 };
    solution.canPartition(nums);
    nums = { 1,2,3,5 };
    solution.canPartition(nums);
    nums = { 3,13,4,6,3,2,16,7,3,4,7};
    solution.canPartition(nums);
}