Perfect Sum Problem (GFG perfect-sum)

Nguồn: GeeksforGeeks (Medium) Độ khó: Trung bình Quy hoạch động Đệ quy có nhớ Đếm

Đề bài

🇻🇳 Tiếng Việt🇬🇧 English (đề gốc)

Perfect Sum Problem – Bài toán tổng hoàn hảo (GeeksforGeeks, Medium)

Cho một mảng arr[] gồm các số nguyên không âm và một số nguyên sum, nhiệm vụ là đếm tất cả các tập con của mảng đã cho có tổng bằng sum cho trước.

Lưu ý: Đáp án có thể rất lớn, nên hãy in ra đáp án chia lấy dư cho $10^9 + 7$.

Ví dụ 1:

Input: N = 6, arr[] = {2, 3, 5, 6, 8, 10}
       sum = 10
Output: 3
Giải thích: {2, 3, 5}, {2, 8}, {10}

Ví dụ 2:

Input: N = 5, arr[] = {1, 2, 3, 4, 5}
       sum = 10
Output: 3
Giải thích: {1, 2, 3, 4}, {1, 4, 5}, {2, 3, 5}

Nhiệm vụ của bạn: Bạn không cần đọc dữ liệu vào hay in gì ra. Hãy hoàn thiện hàm perfectSum() nhận N, mảng arr[] và sum làm tham số đầu vào và trả về một giá trị số nguyên.

Độ phức tạp thời gian mong muốn: $O(N \cdot sum)$.
Bộ nhớ phụ mong muốn: $O(N \cdot sum)$.

Ràng buộc:

• $1 \le N \cdot sum \le 10^6$
• $0 \le arr[i] \le 10^6$

Perfect Sum Problem (GeeksforGeeks, Medium)

Given an array arr[] of non-negative integers and an integer sum, the task is to count all subsets of the given array with a sum equal to a given sum.

Note: Answer can be very large, so, output answer modulo $10^9 + 7$.

Example 1:

Input: N = 6, arr[] = {2, 3, 5, 6, 8, 10}
       sum = 10
Output: 3
Explanation: {2, 3, 5}, {2, 8}, {10}

Example 2:

Input: N = 5, arr[] = {1, 2, 3, 4, 5}
       sum = 10
Output: 3
Explanation: {1, 2, 3, 4}, {1, 4, 5},
             {2, 3, 5}

Your Task: You don't need to read input or print anything. Complete the function perfectSum() which takes N, array arr[] and sum as input parameters and returns an integer value.

Expected Time Complexity: $O(N \cdot sum)$
Expected Auxiliary Space: $O(N \cdot sum)$

Constraints:

• $1 \le N \cdot sum \le 10^6$
• $0 \le arr[I] \le 10^6$

Để chạy thử trên máy (và trong các khung chạy tay bên dưới), mình dùng định dạng nhập: dòng đầu $N$ và $sum$, dòng sau $N$ số của mảng. Ví dụ 1 sẽ là:

Input chạy thử

6 10
2 3 5 6 8 10

Output

3

Lời mở đầu

Bài này mình được một bạn học viên hỏi nên sẵn tiện mình viết bài giải chi tiết để nhiều bạn được tham khảo luôn. Hy vọng mang đến được giá trị cho các bạn 😇. Bài này chính là bài mở rộng từ bài nuôi bò 1 mình đã giải trước đó, nên anh em nào chưa quen cách quay lui (vét cạn bằng đệ quy) thì nên đọc qua bài đó trước nha.

Lưu ý khi nộp trên GeeksforGeeks

Trên GFG ta chỉ cần hoàn thiện hàm perfectSum() mà bài cho thôi: không cần đọc đầu vào, đầu vào đã có sẵn trong tham số, và hàm phải trả về kết quả. Code bên dưới mình có thêm hàm main chỉ để các bạn chạy thử trên máy, khi nộp thì bỏ phần đó đi. GFG thỉnh thoảng đổi khung code (ví dụ tham số thành vector<int>& arr, target), gặp vậy thì các bạn sửa phần khai báo hàm cho khớp, còn ruột thuật toán giữ nguyên.

Về giới hạn thời gian: bài này không ghi thời gian chạy giới hạn, nhưng có đưa ra độ phức tạp mong muốn là $O(N \cdot sum)$ mà $N \cdot sum \le 10^6$, nên anh em cứ cố code bài này chạy dưới 1 giây nha. Nhắc lại: với 1 giây thì toàn bài chỉ nên lặp cỡ $(3 \text{ đến } 5) \cdot 10^7$ lần là an toàn (với C/C++, các ngôn ngữ chậm hơn như Python thì ngưỡng còn thấp hơn).

Tóm tắt lại đề cho dễ hiểu: cho số nguyên dương $N$, $sum$ và mảng arr gồm $N$ số nguyên không âm ($0 \le arr[i] \le 10^6$), biết $1 \le N \cdot sum \le 10^6$. Hãy đếm số tập con của mảng có tổng bằng $sum$ (bản thân cả mảng cũng là một tập con của chính nó), trả về kết quả chia dư cho $10^9 + 7$.

Với ví dụ 1: $N = 6$, $sum = 10$, arr = {2, 3, 5, 6, 8, 10}. Có 3 tập con có tổng bằng 10 là $\{2, 3, 5\}$, $\{2, 8\}$, $\{10\}$ ⇒ kết quả là 3.

Để ý số 0

Mảng có thể chứa số $0$. Các tập con được phân biệt theo vị trí phần tử, nên ví dụ arr = {0, 0, 5}, $sum = 5$ thì có tới 4 tập con: $\{5\}$, $\{0_1, 5\}$, $\{0_2, 5\}$, $\{0_1, 0_2, 5\}$. Tất cả các cách bên dưới đều xử lý đúng chuyện này.

Link nộp bài

Bấm vào nút bên dưới để nộp bài và được hệ thống CLUE OJ chấm tự động.

Nộp bài trên CLUE OJ

Lộ trình lời giải, bấm vào từng phần để nhảy tới:

Cách 1Quay lui · O(2^N) · TLECách 2Đệ quy có nhớ · O(N·sum)Cách 3QHĐ bottom-up → mảng 1 chiều

Cách 1Quay lui: chọn hay không chọn từng phần tử – O(2^N)

Cách dễ nhất chính là vét cạn, thử mọi trường hợp có thể. Ở bài nuôi bò 1, hàm Try() đi thử chọn từng phần tử rồi cộng vào một biến lưu tổng của tập con, sau đó đem so với tổng cần tạo. Ở đây mình viết một hàm Try() có trả về theo hướng ngược lại: tổng cần tạo ra là $sum$, vậy mỗi khi chọn một phần tử thì ta đem nó trừ vào biến $sum$; đến cuối mà $sum = 0$ thì chứng tỏ ta đã có 1 tập con có tổng bằng $sum$ ban đầu.

• Hàm Try(i, sum, arr, n) trả về số tập con lấy từ các phần tử ở vị trí $i$ tới $n - 1$ có tổng bằng sum (mảng lưu từ $0$ tới $n - 1$). arr và n là 2 biến đi kèm để mang theo mảng và số phần tử: vì ta đang viết hàm cho bài nên không khai báo chúng là biến toàn cục được, phải truyền vào.
• Điều kiện dừng: khi i == n là đã xét hết các phần tử. Nếu sum == 0 thì tập con vừa lựa có tổng đúng bằng yêu cầu ⇒ return 1; ngược lại return 0.
• Nếu arr[i] > sum: không thể chọn arr[i] được, nên kết quả chính là số tập con trong khoảng $i + 1$ tới $n - 1$ có tổng bằng sum: return Try(i + 1, sum, arr, n).
• Ngược lại arr[i] <= sum: ta có thể chọn hoặc không chọn arr[i]. Nếu chọn thì phần còn lại chỉ cần có tổng sum - arr[i]; nếu không chọn thì phần còn lại vẫn cần tổng sum. Cộng 2 trường hợp: return Try(i + 1, sum - arr[i], arr, n) + Try(i + 1, sum, arr, n).

Nhớ chia dư ở mỗi lần return

Kết quả có thể rất lớn. Theo tính chất đồng dư $(a + b) \bmod m = \big((a \bmod m) + (b \bmod m)\big) \bmod m$, nên thay vì tính ra kết quả rồi mới chia dư (dễ tràn số), ta chia dư ở mỗi lần return. Hai số hạng đều $\lt 10^9 + 7$ nên tổng $\lt 2 \cdot 10^9 + 14$, vẫn vừa kiểu int (tối đa $\approx 2.147 \cdot 10^9$).

Hàm perfectSum chỉ việc gọi Try(0, sum, arr, n), vì ta cần số tập con có tổng bằng sum trong khoảng từ $0$ tới $n - 1$. Source code cho anh em nào cần tham khảo ý tưởng trên:

#include <bits/stdc++.h>
using namespace std;
const int mod = (int)1e9 + 7;

int Try(int i, int sum, int arr[], int n){
    if(i == n){
        if(sum == 0){
            return 1;
        }
        return 0;
    }
    if(arr[i] > sum){
        return Try(i + 1, sum, arr, n) % mod;
    }
    return (Try(i + 1, sum - arr[i], arr, n) + Try(i + 1, sum, arr, n)) % mod;
}

class Solution{
public:
    int perfectSum(int arr[], int n, int sum){
        return Try(0, sum, arr, n);
    }
};

// Phần main chỉ để chạy thử trên máy, nộp GFG thì chỉ cần phần ở trên
int main(){
    int n, sum;
    cin >> n >> sum;
    int arr[n];
    for(int i = 0; i < n; ++i){
        cin >> arr[i];
    }
    Solution ob;
    cout << ob.perfectSum(arr, n, sum);
    return 0;
}

import sys

mod = 10**9 + 7

def Try(i, s, arr, n):
    if i == n:
        if s == 0:
            return 1
        return 0
    if arr[i] > s:
        return Try(i + 1, s, arr, n) % mod
    return (Try(i + 1, s - arr[i], arr, n) + Try(i + 1, s, arr, n)) % mod

class Solution:
    def perfectSum(self, arr, n, s):
        return Try(0, s, arr, n)

# Phần dưới chỉ để chạy thử trên máy
if __name__ == '__main__':
    sys.setrecursionlimit(10000)
    data = sys.stdin.read().split()
    n, s = int(data[0]), int(data[1])
    arr = list(map(int, data[2:2 + n]))
    print(Solution().perfectSum(arr, n, s))

C++▶ Chạy tay từng dòng codeTry(i, sum): số tập con của arr[i..n-1] có tổng = sum; chọn arr[i] thì trừ vào sum.

Dữ liệu vào (stdin) – sửa thoải mái3 5 2 3 5

Dữ liệu mẫu:

1#include <bits/stdc++.h>

2using namespace std;

3const int mod = (int)1e9 + 7;

4

5int Try(int i, int sum, int arr[], int n){

6 if(i == n){

7 if(sum == 0){

8 return 1;

9 }

10 return 0;

11 }

12 if(arr[i] > sum){

13 return Try(i + 1, sum, arr, n) % mod;

14 }

15 return (Try(i + 1, sum - arr[i], arr, n) + Try(i + 1, sum, arr, n)) % mod;

16}

17

18class Solution{

19public:

20 int perfectSum(int arr[], int n, int sum){

21 return Try(0, sum, arr, n);

22 }

23};

24

25// Phần main chỉ để chạy thử trên máy, nộp GFG thì chỉ cần phần ở trên

26int main(){

27 int n, sum;

28 cin >> n >> sum;

29 int arr[n];

30 for(int i = 0; i < n; ++i){

31 cin >> arr[i];

32 }

33 Solution ob;

34 cout << ob.perfectSum(arr, n, sum);

35 return 0;

36}

ChậmVừaNhanhRất nhanh

Đánh giá độ phức tạp của cách làm này:

• Không gian: $O(N)$, vì ta chỉ dùng mỗi mảng arr (cộng độ sâu đệ quy tối đa $N$ tầng).
• Thời gian: $O(2^N)$, vì ở mỗi phần tử ta đều có 2 lựa chọn, $N$ phần tử thì có tới $2^N$ lựa chọn.

Không gian$O(N)$

Thời gian$O(2^N)$

TLE

Với cách trên thì chắc chắn sẽ bị TLE, khi mình nộp thì bị TLE ở test 104 / 323 nha.

Cách 2Đệ quy có nhớ (QHĐ top-down) – O(N·sum)

Giờ ta cải tiến cách trên. Ta nhận ra bài toán có rất nhiều bài toán con trùng lặp: ví dụ một lần ta đã tính ra Try(1, 1, arr, n), lần sau gặp lại Try(1, 1, arr, n) ta vẫn đi tính lại, rất tốn thời gian. Và mỗi lần gọi Try(i, sum, arr, n) thì arr, n không đổi, chỉ có i và sum thay đổi.

Nên ta tạo một mảng 2 chiều F[n][sum + 1] lưu kết quả các lần gọi Try(i, sum, arr, n): $i$ nằm trong khoảng $0$ tới $n - 1$ nên kích thước là [n]; còn trong quá trình đệ quy biến sum chỉ giảm dần, luôn nằm trong khoảng $0$ tới $sum$ ban đầu, nên [sum + 1] là đủ.

• Lúc đầu lấp đầy F bằng $-1$. Nếu F[i][sum] != -1 thì Try(i, sum, arr, n) đã tính rồi, chỉ việc return F[i][sum].
• Ngược lại thì gọi đệ quy để tính, nhớ gán vào F[i][sum] rồi hẵng return, để lần sau gặp lại thì trả về luôn mà không phải tính.

Ý chính

Đây chính là quy hoạch động top-down, hay còn gọi là đệ quy có nhớ: lưu kết quả các lần đệ quy để tránh tính đi tính lại một việc đã tính. Tốn thêm bộ nhớ nhưng thời gian nhanh hơn rất nhiều.

#include <bits/stdc++.h>
using namespace std;
const int mod = (int)1e9 + 7;

int Try(int i, int sum, int arr[], int n, vector<vector<int>> &f){
    if(i == n){
        if(sum == 0){
            return 1;
        }
        return 0;
    }
    if(f[i][sum] != -1){
        return f[i][sum];
    }
    if(arr[i] > sum){
        return f[i][sum] = Try(i + 1, sum, arr, n, f) % mod;
    }
    return f[i][sum] = (Try(i + 1, sum - arr[i], arr, n, f) + Try(i + 1, sum, arr, n, f)) % mod;
}

class Solution{
public:
    int perfectSum(int arr[], int n, int sum){
        vector<vector<int>> f(n, vector<int>(sum + 1, -1));
        return Try(0, sum, arr, n, f);
    }
};

// Phần main chỉ để chạy thử trên máy, nộp GFG thì chỉ cần phần ở trên
int main(){
    int n, sum;
    cin >> n >> sum;
    int arr[n];
    for(int i = 0; i < n; ++i){
        cin >> arr[i];
    }
    Solution ob;
    cout << ob.perfectSum(arr, n, sum);
    return 0;
}

import sys
import threading

mod = 10**9 + 7

def Try(i, s, arr, n, f):
    if i == n:
        if s == 0:
            return 1
        return 0
    if f[i][s] != -1:
        return f[i][s]
    if arr[i] > s:
        f[i][s] = Try(i + 1, s, arr, n, f) % mod
        return f[i][s]
    f[i][s] = (Try(i + 1, s - arr[i], arr, n, f) + Try(i + 1, s, arr, n, f)) % mod
    return f[i][s]

class Solution:
    def perfectSum(self, arr, n, s):
        f = [[-1] * (s + 1) for _ in range(n)]
        return Try(0, s, arr, n, f)

# Phần dưới chỉ để chạy thử trên máy (đệ quy sâu tới n tầng nên nới giới hạn)
def main():
    data = sys.stdin.read().split()
    n, s = int(data[0]), int(data[1])
    arr = list(map(int, data[2:2 + n]))
    print(Solution().perfectSum(arr, n, s))

if __name__ == '__main__':
    sys.setrecursionlimit(1 << 21)
    threading.stack_size(1 << 29)
    t = threading.Thread(target=main)
    t.start()
    t.join()

Giải thích một số chỗ trong code:

• vector<vector<int>> f(n, vector<int>(sum + 1, -1)); mình dùng vector cho tiện truyền vào hàm, và gán mọi phần tử bằng $-1$ cũng rất dễ. Anh em cứ xem nó như mảng 2 chiều nha.
• vector<vector<int>> &f ở phần khai báo hàm: nhớ thêm tham chiếu &. Thường mình khai báo f là mảng toàn cục, nhưng ở đây ta đang viết hàm và $N \cdot sum$ có thể tới $10^6$, nên khai báo trong hàm rồi truyền tham chiếu, vừa cập nhật được f như biến toàn cục, vừa không phải copy lại cả mảng mỗi lần gọi.
• return f[i][sum] = …; nghĩa là gán f[i][sum] = … rồi mới return f[i][sum].

Đánh giá độ phức tạp của cách làm này:

• Không gian: $O(N \cdot sum)$ cho vector f (thêm mảng arr nữa nhưng theo quy tắc Big-O vẫn là $O(N \cdot sum)$).
• Thời gian: $O(N \cdot sum)$, vì trường hợp xấu nhất ta chỉ lấp đầy toàn bộ mảng F, mỗi ô tính đúng một lần với chi phí $O(1)$.

Không gian$O(N \cdot sum)$

Thời gian$O(N \cdot sum)$

Vậy với cải tiến từ vét cạn thành đệ quy có nhớ, ta đã AC (Accepted) bài này rồi 🎉.

Độ sâu đệ quy

Đệ quy sâu tới $N$ tầng, mà $N$ có thể lên tới $10^6$ (khi $sum = 1$). Mình chạy thử trên máy với stack mặc định 8 MB thì trường hợp $N = 10^6$ bản C++ bị tràn stack (cho stack lớn hơn thì chạy đúng, khoảng 0.5 giây); trên GFG thì code này vẫn AC. Bản Python mình phải nới giới hạn đệ quy và chạy trong một thread có stack lớn. Đây cũng là lý do mình thích cách 3 hơn: không đệ quy nên không lo chuyện này.

Cách 3QHĐ bottom-up, rồi rút gọn còn mảng 1 chiều – O(N·sum)

Ngoài cách trên, ta còn có thể dùng quy hoạch động bottom-up, tức là xây công thức truy hồi rồi lấp bảng bằng vòng lặp. Cho anh em đã biết cơ bản về quy hoạch động thì ta có 4 bước:

Bước 1 – Bài toán con: gọi F[i][j] ($0 \le i \le n$, $0 \le j \le sum$) là số tập con có tổng bằng $j$ khi xét $i$ phần tử đầu tiên. Lưu ý là xét $i$ phần tử đầu tiên nha: $i = 1$ tức là đang xét phần tử arr[0].

Bước 2 – Bài toán cơ sở: nếu không xét phần tử nào ($i = 0$) thì ta chỉ có 1 tập rỗng, mà tập rỗng thì có tổng bằng $0$ ⇒ F[0][0] = 1, còn F[0][1] tới F[0][sum] đều bằng $0$.

Bước 3 – Đáp án: hiển nhiên là F[n][sum], số tập con có tổng bằng $sum$ khi xét cả $n$ phần tử.

Bước 4 – Công thức truy hồi: khi xét phần tử thứ $i$ (trong mảng là arr[i - 1] vì mảng lưu từ $0$) với tổng cần là $j$:

• arr[i - 1] > j: không thể chọn phần tử thứ $i$, nên số tập con giống hệt khi xét $i - 1$ phần tử: F[i][j] = F[i - 1][j].
• arr[i - 1] <= j: có thể không lấy (giống trên, F[i - 1][j] tập) hoặc có lấy phần tử thứ $i$. Nếu lấy thì $i - 1$ phần tử trước đó cần có tổng $j - arr[i - 1]$, cộng thêm arr[i - 1] mới bằng $j$ ⇒ F[i - 1][j - arr[i - 1]] tập. Vậy F[i][j] = F[i - 1][j] + F[i - 1][j - arr[i - 1]].

Công thức truy hồi

Nếu $arr[i - 1] \gt j$: $F[i][j] = F[i - 1][j]$.
Nếu $arr[i - 1] \le j$: $F[i][j] = F[i - 1][j] + F[i - 1][j - arr[i - 1]]$ (nhớ chia dư cho $10^9 + 7$).

#include <bits/stdc++.h>
using namespace std;
const int mod = (int)1e9 + 7;

class Solution{
public:
    int perfectSum(int arr[], int n, int sum){
        vector<vector<int>> f(n + 1, vector<int>(sum + 1));
        f[0][0] = 1;
        for(int j = 1; j <= sum; ++j){
            f[0][j] = 0;
        }
        for(int i = 1; i <= n; ++i){
            for(int j = 0; j <= sum; ++j){
                if(arr[i - 1] > j){
                    f[i][j] = f[i - 1][j];
                }
                else{
                    f[i][j] = f[i - 1][j] + f[i - 1][j - arr[i - 1]];
                }
                f[i][j] %= mod;
            }
        }
        return f[n][sum];
    }
};

// Phần main chỉ để chạy thử trên máy, nộp GFG thì chỉ cần phần ở trên
int main(){
    int n, sum;
    cin >> n >> sum;
    int arr[n];
    for(int i = 0; i < n; ++i){
        cin >> arr[i];
    }
    Solution ob;
    cout << ob.perfectSum(arr, n, sum);
    return 0;
}

import sys

mod = 10**9 + 7

class Solution:
    def perfectSum(self, arr, n, s):
        f = [[0] * (s + 1) for _ in range(n + 1)]
        f[0][0] = 1
        for i in range(1, n + 1):
            a = arr[i - 1]
            for j in range(s + 1):
                if a > j:
                    f[i][j] = f[i - 1][j]
                else:
                    f[i][j] = (f[i - 1][j] + f[i - 1][j - a]) % mod
        return f[n][s]

# Phần dưới chỉ để chạy thử trên máy
if __name__ == '__main__':
    data = sys.stdin.read().split()
    n, s = int(data[0]), int(data[1])
    arr = list(map(int, data[2:2 + n]))
    print(Solution().perfectSum(arr, n, s))

Mình đổi mảng tĩnh sang vector

Bản gốc mình khai báo int f[n + 1][sum + 1]; ngay trong hàm. Nhưng khi $N = 1$, $sum = 10^6$ thì mảng đó cỡ 8 MB nằm trên stack, dễ bị tràn stack, nên ở đây mình đổi sang vector (cấp phát trên heap) cho an toàn, logic giữ nguyên.

So với đệ quy có nhớ thì cách này nhanh hơn và đỡ tốn bộ nhớ hơn vì không mất không gian và thời gian cho đệ quy nữa, nhưng theo Big-O thì độ phức tạp vẫn là $O(N \cdot sum)$.

Rút gọn còn mảng 1 chiều – nhớ duyệt ngược!

Thậm chí bài này ta còn cải tiến cho ăn ít bộ nhớ hơn nữa: chỉ dùng một mảng 1 chiều F[sum + 1], với F[j] là số tập con có tổng bằng $j$ (tính tới các phần tử đã xét). Ban đầu F[0] = 1 (có sẵn 1 tập rỗng tổng bằng 0), F[1] tới F[sum] bằng $0$ vì chưa xét phần tử nào.

Ta vẫn đi lần lượt từng phần tử arr[i]. Nếu $j \ge arr[i]$ thì số tập con có tổng bằng $j$ được cộng thêm số tập con có tổng bằng $j - arr[i]$, vì mỗi tập như vậy thêm phần tử arr[i] vào là có tổng $j$: F[j] += F[j - arr[i]].

Duyệt j tăng dần là SAI

Nếu làm vòng $i$ từ $0$ tới $n - 1$, còn $j$ từ arr[i] tăng lên tới $sum$ thì sai. Ví dụ $n = 2$, $sum = 6$, arr = {2, 3}: ban đầu F = {1, 0, 0, 0, 0, 0, 0}. Duyệt tăng thì sau khi xét xong arr[0] = 2, mảng thành {1, 0, 1, 0, 1, 0, 1}. Anh em thấy cấn rồi chứ: mới xét một phần tử, làm sao có tập con tổng bằng 4 hay bằng 6 được? Chỉ có đúng một tập tổng bằng 2 thôi. Lý do: vừa cho F[2] = 1 xong, tới F[4] lại cộng F[4 - 2] = F[2] (đã chứa phần tử thứ nhất), tức là lấy phần tử thứ nhất 2 lần.
Cách khắc phục: duyệt ngược $j$ từ $sum$ về arr[i]. Khi đó F[j - arr[i]] (chỉ số nhỏ hơn) chưa bị cập nhật ở lượt này, vẫn là giá trị "trước khi xét arr[i]", đúng như F[i - 1][j - arr[i - 1]] của bảng 2 chiều.

Minh hoạ: duyệt ngược và duyệt xuôi

Em nhập mảng, $sum$ và chọn chiều duyệt rồi bấm Tiếp: ô cam là F[j] đang cập nhật, ô xanh dương là F[j - arr[i]] được cộng vào. Chọn "Duyệt xuôi (sai)" với ví dụ {2, 3}, $sum = 6$ để thấy lỗi lấy một phần tử nhiều lần (ô đỏ).

arr sum Chiều duyệt Duyệt ngược (đúng)Duyệt xuôi (sai)

Ví dụ nhanh:

Source code cho anh em nào cần tham khảo cách mảng 1 chiều:

#include <bits/stdc++.h>
using namespace std;
const int mod = (int)1e9 + 7;

class Solution{
public:
    int perfectSum(int arr[], int n, int sum){
        vector<int> f(sum + 1);
        f[0] = 1;
        for(int i = 1; i <= sum; ++i){
            f[i] = 0;
        }
        for(int i = 0; i < n; ++i){
            for(int j = sum; j >= arr[i]; --j){
                f[j] += f[j - arr[i]];
                f[j] %= mod;
            }
        }
        return f[sum];
    }
};

// Phần main chỉ để chạy thử trên máy, nộp GFG thì chỉ cần phần ở trên
int main(){
    int n, sum;
    cin >> n >> sum;
    int arr[n];
    for(int i = 0; i < n; ++i){
        cin >> arr[i];
    }
    Solution ob;
    cout << ob.perfectSum(arr, n, sum);
    return 0;
}

import sys

mod = 10**9 + 7

class Solution:
    def perfectSum(self, arr, n, s):
        f = [0] * (s + 1)
        f[0] = 1
        for i in range(n):
            a = arr[i]
            for j in range(s, a - 1, -1):
                f[j] = (f[j] + f[j - a]) % mod
        return f[s]

# Phần dưới chỉ để chạy thử trên máy
if __name__ == '__main__':
    data = sys.stdin.read().split()
    n, s = int(data[0]), int(data[1])
    arr = list(map(int, data[2:2 + n]))
    print(Solution().perfectSum(arr, n, s))

C++▶ Chạy tay từng dòng codeMảng 1 chiều f[j]: với mỗi arr[i], duyệt j từ sum về arr[i], f[j] += f[j − arr[i]].

Dữ liệu vào (stdin) – sửa thoải mái6 10 2 3 5 6 8 10

Dữ liệu mẫu:

1#include <bits/stdc++.h>

2using namespace std;

3const int mod = (int)1e9 + 7;

4

5class Solution{

6public:

7 int perfectSum(int arr[], int n, int sum){

8 vector<int> f(sum + 1);

9 f[0] = 1;

10 for(int i = 1; i <= sum; ++i){

11 f[i] = 0;

12 }

13 for(int i = 0; i < n; ++i){

14 for(int j = sum; j >= arr[i]; --j){

15 f[j] += f[j - arr[i]];

16 f[j] %= mod;

17 }

18 }

19 return f[sum];

20 }

21};

22

23// Phần main chỉ để chạy thử trên máy, nộp GFG thì chỉ cần phần ở trên

24int main(){

25 int n, sum;

26 cin >> n >> sum;

27 int arr[n];

28 for(int i = 0; i < n; ++i){

29 cin >> arr[i];

30 }

31 Solution ob;

32 cout << ob.perfectSum(arr, n, sum);

33 return 0;

34}

ChậmVừaNhanhRất nhanh

Đánh giá độ phức tạp của cách làm này:

• Không gian: bảng 2 chiều tốn $O(N \cdot sum)$; bản mảng 1 chiều chỉ còn $O(sum)$.
• Thời gian: vẫn $O(N \cdot sum)$ cho cả hai bản, với $N \cdot sum \le 10^6$ thì chạy vèo vèo.

Không gian$O(sum)$

Thời gian$O(N \cdot sum)$

Ghi chú của mình: code C++ và Python của cả 4 bản (quay lui, đệ quy có nhớ, bảng 2 chiều, mảng 1 chiều) đã được kiểm tra với 300 bộ test ngẫu nhiên nhỏ (có nhiều số 0), so với code duyệt mọi tập con – khớp hết; test 999 số 0 và một số 1000 (đáp án $2^{999} \bmod (10^9 + 7)$) cũng ra đúng. Với $N \cdot sum = 10^6$: bản mảng 1 chiều C++ chạy dưới 0.25 giây, Python dưới 1 giây; riêng đệ quy có nhớ với $N = 10^6$ thì bản C++ bị tràn stack 8 MB trên máy mình như đã nói ở trên.

Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này. Anh em đọc chắc cũng mỏi mắt luôn chứ 😅 vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 🤪. Vậy nên đừng tiếc gì cho mình một lời bình luận hoặc chia sẻ bài viết để động viên mình nè. Chúc anh em học tốt và gặt hái nhiều thành công 😇