LeetCode416. Tách tập hợp bằng nhau

Liên kết bài toán: 416. Tách tập hợp bằng nhau

Mô tả bài toán:

Cho một mảng số nguyên dương không rỗng nums. Hãy xác định liệu có thể chia mảng thành hai tập con sao cho tổng các phần tử trong từng tập bằng nhau.

Ví dụ 1:

<strong>Input:</strong> nums = [1,5,11,5]
<strong>Output:</strong> true
<strong>Giải thích:</strong> Mảng có thể chia thành [1, 5, 5] và [11].

Ví dụ 2:

<strong>Input:</strong> nums = [1,2,3,5]
<strong>Output:</strong> false
<strong>Giải thích:</strong> Không thể chia mảng thành hai tập con có tổng bằng nhau.

Gợi ý:

• 1 <= nums.length <= 200
• 1 <= nums[i] <= 100

Phân tích thuật toán:

Xác định mảng trạng thái và ý nghĩa chỉ số:

dp[i][j] biểu thị giá trị lớn nhất không vượt quá j khi chọn các phần tử từ 0~i.

Công thức truy hồi:

dp[i][j] = max(dp[i-1][j], dp[i-1][j-nums[i]] + nums[i])

Khởi tạo:

Tổng của tập con không thể vượt quá tổng mảng chia đôi, do đó chiều dài chiều giá trị của mảng dp được thiết lập thành nửa tổng.

vector<vector<int>>dp(nums.size(), vector<int>(sum + 1, 0));
        for(int i = nums[0]; i <= sum; i++) {
            dp[0][i] = nums[0];
        }

Thứ tự duyệt:

Vòng lặp phần tử nằm ngoài, vòng lặp tổng giá trị nằm bên trong.

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int sum = 0;
        for(int i = 0; i < nums.size(); i++) {
            sum += nums[i];
        }
        if(sum % 2 != 0) return false;
        sum /= 2;

        vector<vector<int>>dp(nums.size(), vector<int>(sum + 1, 0));
        for(int i = nums[0]; i <= sum; i++) {
            dp[0][i] = nums[0];
        }

        for(int i = 1; i < nums.size(); i++) {
            for(int j = 0; j <= sum; j++) {
                if(j < nums[i]) dp[i][j] = dp[i - 1][j];
                else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - nums[i]] + nums[i]);
                if(dp[i][j] == sum) return sum;
            }
        }
        return false;

    }
};

Tối ưu hóa không gian bằng cách chuyển đổi mảng 2D sang mảng 1D (vòng lặp tổng giá trị cần chạy ngược):

class Solution{
    public boolean canPartition(int[] nums) {
        int sum = 0;
        for(int i = 0; i < nums.length; i++) 
        sum += nums[i];
        if(sum % 2 != 0) return false;
        sum /= 2;
        int[] dp = new int[sum + 1];
        for(int i = nums[0]; i <= sum; i++)
        dp[i] = nums[0];
        for(int i = 1; i < nums.length; i++) {
            for(int j = sum; j >= nums[i]; j--) {
                dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i]);
            }
            if(dp[sum] == sum) return true;
        }
        return false;
    }
}

Tổng kết:

Các bài toán tương tự có thể được xử lý như bài toán túi xách, xác định rõ dung lượng túi và vật phẩm tương ứng.