---
title: QUAY LUI - Lời giải
---

[QUAY LUI] - Lời giải
===

-----

###### 📋 Content:

[TOC]

-----
# Lời giải
## Bài 1
- Trong quá trình quay lui, ta tạo hàm `Per(int i, int mass, int sum)` nhằm lưu giá trị và trọng lượng của các vật bỏ vào túi. Ta nhận xét mỗi đồ vật đều chỉ có $2$ trạng thái là **lấy** hoặc **không lấy** (**sinh nhị phân**). Sau khi chạy đến vị trí $n+1$ thì ta sẽ dừng lại và xét. Nếu thỏa $mass$ $\le$ $m$ và cập nhật nếu như $sum$ $\ge$ $ans$ (biến đáp án).
- Độ Phức Tạp: $O(2^n)$
- Code mẫu:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll const N = 1000005;
ll n, m, value[100], mas = 0, t, res, w[100], v[100], per[N];
vector<ll> ans;

void Per(ll i, ll mass, ll sum) {
  if (i > n) {
    if (mass <= m && sum > mas) {
      ans.clear();
      for (int j = 1; j <= n; j++)
        if (per[j] == 1) ans.push_back(j);
      mas = sum;
    }
    return;
  }
  for (int j = 0; j <= 1; j++) {
    per[i] = j;
    Per(i + 1, mass + per[i] * w[i], sum + per[i] * v[i]);
  }
}

signed main() {
  cin.tie(0)->sync_with_stdio(0);
  cin >> n >> m;
  for (int i = 1; i <= n; i++) cin >> w[i] >> v[i];
  per[0] = 0;
  Per(1, 0, 0);
  cout << ans.size() << "\n";
  for (int i = 0; i < ans.size(); i++) cout << ans[i] << " ";
}

## Bài 2

- Ý tưởng là tạo ra tất cả các dãy ngoặc đúng bằng cách liên tục thêm các ngoặc mở và đóng vào chuỗi, tạo thành các chuỗi con khác nhau. Ta bắt đầu với một chuỗi rỗng và số lượng ngoặc mở và ngoặc đóng là $0$. Bằng cách sử dụng kỹ thuật đệ quy, ta tạo ra tất cả các chuỗi con có thể từ chuỗi ban đầu, đồng thời kiểm tra xem chuỗi đó có phải là dãy ngoặc đúng hay không.

- Khi độ dài của chuỗi đạt tới $n$, thuật toán kiểm tra xem chuỗi đó có phải là dãy ngoặc. Nếu đúng, chuỗi được thêm vào kết quả.

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

vector<string> ans;

// Kiểm tra xem một chuỗi có phải là dãy ngoặc đúng không
bool check(string str) {
  int res = 0;
  for (int i = 0; i < str.length(); i++) {
    if (str[i] == '(') {
      res++;
    } else {
      res--;
      if (res < 0) {
        return false;
      }
    }
  }
  return (res == 0);
}

// Hàm đệ quy để tạo ra tất cả các dãy ngoặc đúng
void solve(int n, int open, int close, string str) {
  // Nếu độ dài của chuỗi đạt tới giá trị n, kiểm tra xem chuỗi đó có phải là
  // dãy ngoặc đúng không,
  // nếu đúng thì push chuỗi đó vào ans
  if (str.length() == n) {
    if (check(str)) {
      ans.push_back(str);
    }
    return;
  }

  // Nếu số lượng ngoặc mở chưa đủ, tạo một ngoặc mở mới và gọi đệ quy với tham
  // số open+1
  if (open < n / 2) {
    solve(n, open + 1, close, str + "(");
  }

  // Nếu số lượng ngoặc đóng chưa đủ và số lượng ngoặc mở hiện tại lớn hơn số
  // lượng ngoặc đóng hiện tại,
  // tạo một ngoặc đóng mới và gọi đệ quy với tham số close+1
  if (close < open) {
    solve(n, open, close + 1, str + ")");
  }
}

int main() {
  cin.tie(0)->sync_with_stdio(0);
  int n;
  cin >> n;
  solve(n, 0, 0, "");
  cout << ans.size() << '\n';
  for (auto s : ans) cout << s << '\n';
}

## Bài 3
- Tạo mảng $a_i$ lưu lại mệnh giá của các tờ tiền. Sau đó tạo một hàm `Per()` chạy quay lui qua tất cả các trường hợp. Nhận xét mỗi tờ tiền đều chỉ có $2$ trạng thái là **lấy** hoặc **không lấy** (**sinh nhị phân**). Nếu như số lượng đồng tiền lấy trong quá trình chạy quay lui nhiều hơn số tiền có trong máy ATM, ta dừng hàm `Per()` và chạy truy vết các phần tử trong mảng $per_i$ và xuất ra màn hình.
- Độ Phức Tạp: $O(2^n)$
- Code mẫu:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll const N = 100005;
ll n, per[N], a[N], cnt, k;

void Per(ll i, ll sum) {
  if (i > n) {
    if (sum == k) {
      cnt = 0;
      for (int i = 1; i <= n; i++)
        if (per[i] != 0) cnt++;
      cout << cnt << "\n";
      for (int i = 1; i <= n; i++)
        if (per[i] != 0) cout << i << " ";
      exit(0);
    }
    return;
  }
  for (int j = 0; j <= 1; j++) {
    per[i] = j;
    Per(i + 1, sum + a[i] * per[i]);
  }
}

signed main() {
  cin.tie(0)->sync_with_stdio(0);
  cin >> n >> k;
  for (int i = 1; i <= n; i++) cin >> a[i];
  Per(1, 0);
  cout << "khongtherut";
}

## Bài 4
- Tạo mảng $x_i$ để lưu các phần từ trong một hoán vị mà bạn có thể sinh ra. Tạo hàm `go()` gồm hai biến là `go(long long i, long long sum` để lưu số lượng số trong mảng $x_i$ cũng như tổng của chúng. Nếu $sum \ge n$ thì ta dừng lại và xét, nếu $sum=n$ thì ta truy vết và xuất ra các phần tử.
- Độ Phức Tạp: $O(N^2)$
- Code mẫu:

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

int x[40], n;

void go(int i, int sum = 0) {
    if (sum >= n) {
        if (sum == n) {
            cout << n << " = ";
            cout << x[1];
            for (int j = 2; j < i; ++j) cout << '+' << x[j];
            cout << '\n';
        }
        return;
    }
    for (int j = x[i - 1]; j <= n; ++j) {
        x[i] = j;
        go(i + 1, sum + j);
    }
}

signed main() {
    cin.tie(0) -> sync_with_stdio(0);
    cin >> n;
    x[0] = 1;
    go(1);
}
    

## Bài 5
- Tạo hàm quay lui `Per()` mang hai giá trị là `Per(long long i, long long sum)` để lưu lại số lượng con bò đã xét qua. Ta chạy qua tất cả các trường hợp chọn bò để vắt. Nếu $sum \ge k$ ta xét nếu $sum=k$ thì nhập vào `vector<long long> ans`. Cuối cùng xuất ra số lượng phần tử và phần tử nhỏ nhất trong `ans`.
- Độ Phức Tạp: $O(N^2)$
- Code mẫu:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll const N = 1000005;
ll n, k, a[N], res, per[N], cnt[2];
vector<ll> ans;

void Per(ll i, ll sum) {
  if (sum >= k) {
    if (sum == k) ans.push_back(i - 1);
    return;
  }
  for (int j = per[i - 1] + 1; j <= n; j++) {
    per[i] = j;
    Per(i + 1, sum + a[j]);
  }
}

signed main() {
  cin.tie(0)->sync_with_stdio(0);
  cin >> n >> k;
  for (int i = 1; i <= n; i++) cin >> a[i];
  Per(1, 0);
  ll s = ans.size();
  res = LLONG_MAX;
  for (int i = 0; i < s; i++) res = min(res, ans[i]);
  if (s == 0)
    cout << s;
  else
    cout << s << " " << res;
}