Hướng giải của Tổng tập con

Nhớ rằng hướng dẫn giải này chỉ nên sử dụng khi bế tắc, và tuyệt đối không nên sao chép mã nguồn kèm theo. Hãy tôn trọng tác giả bài tập và người viết hướng dẫn giải.
Nộp mã nguồn lời giải chính thức trước khi giải bài tập đó có thể khiến bạn bị ban.

Ý tưởng: Với mỗi phần tử i, thử 2 nhánh: không chọn (gọi backtrack(i+1, cur)) hoặc chọn (gọi backtrack(i+1, cur + a[i])). Cắt tỉa: nếu cur > S thì dừng.

Độ phức tạp: \(O(2^n)\) thời gian, \(O(n)\) bộ nhớ stack.

C++

#include <bits/stdc++.h>
using namespace std;

int n;
long long s, a[20];

bool backtrack(int i, long long cur) {
    if (cur == s) return true;
    if (i == n || cur > s) return false;
    if (backtrack(i + 1, cur)) return true;
    if (backtrack(i + 1, cur + a[i])) return true;
    return false;
}

int main() {
    cin >> n >> s;
    for (int i = 0; i < n; i++) cin >> a[i];
    cout << (backtrack(0, 0) ? "YES" : "NO") << "\n";
    return 0;
}

Python

def backtrack(i, cur):
    if cur == s:
        return True
    if i == n or cur > s:
        return False
    if backtrack(i + 1, cur):
        return True
    if backtrack(i + 1, cur + a[i]):
        return True
    return False

n, s = map(int, input().split())
a = list(map(int, input().split()))
print("YES" if backtrack(0, 0) else "NO")

Nhận xét

Không có ý kiến tại thời điểm này.