## Bài 1: [Tổng tập con 2](https://marisaoj.com/problem/329)
- Chia mảng $A$ thành 2 phần: $A[1...\frac{n}{2}]$ và $A[\frac{n}{2} + 1...n]$.
- Với mỗi phần, quay lui để sinh ra toàn bộ tổng các tập con. Ví dụ: $\{1, 2\}$ sinh ra được tập $\{0, 1, 2, 3\}$. Với nửa đầu gọi tập này là $S_1$, nửa sau gọi là $S_2$. Xét $x$ là một giá trị trong $S_1$, chỉ cần kiểm tra xem có tồn tại $k - x$ trong $S_2$ không.

Code
:::spoiler

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

#define int long long

int n, k;
int a[43];

void backtracking(int i, int target, int sum, unordered_set<int> &s){
    if(i == target){
        s.insert(sum);
        return;
    }

    backtracking(i + 1, target, sum, s);
    backtracking(i + 1, target, sum + a[i], s);
}

signed main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    cin >> n >> k;
    for(int i = 1; i <= n; i++) cin >> a[i];

    unordered_set<int> s1, s2;

    backtracking(1, n / 2 + 1, 0, s1);
    backtracking(n / 2 + 1, n + 1, 0, s2);

    for(auto &x : s1){
        if(s2.count(k - x)){
            cout << "YES";
            return 0;
        }
    }

    cout << "NO";
}

:::

## Bài 2: [Robot](https://marisaoj.com/problem/113)
- Tương tự bài trên, cũng chia các lệnh ra là hai tập nhỏ, thực hiện quay lui để sinh ra hai tập $S_1$, $S_2$ là vị trí của robot. Xét tọa độ $(x,y)$ trong $S_1$, cần kiểm tra xem có bao nhiêu lần $(a-x,b-y)$ xuất hiện trong $S_2$.

Code
:::spoiler

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int Sz = 50;
const int mod = 1e9 + 7;
 
void FastRead(){
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
}
 
int n, a, b, x[Sz], y[Sz];
 
void bt(int i, int target, int sumx, int sumy, map<pair<int, int>, int> &m){
	if (i == target){
		m[{sumx, sumy}]++;
		return;
	}
	
	bt(i + 1, target, sumx, sumy, m);
	bt(i + 1, target, sumx + x[i], sumy + y[i], m);
}
 
signed main(){
	FastRead();
	cin >> n >> a >> b;
	for (int i = 1; i <= n; i++){
		cin >> x[i] >> y[i];
	}
	
	map<pair<int, int>, int> m1, m2;
	bt(1, n/2 + 1, 0, 0, m1);
	bt(n/2 + 1, n + 1, 0, 0, m2);
	
	int ans = 0;
	for (auto it : m1){
		ans += m2[{a - it.first.first, b - it.first.second}] * it.second;
	}
	cout << ans;
	
	return 0;
}

:::

## Bài 3: [Chênh lệch nhỏ nhất](https://marisaoj.com/module/16)
- Gọi $S$ là tổng tất cả các phần tử. Dễ thấy nếu chọn được một tập có tổng gần $\frac{S}{2}$ nhất thì chênh lệch giữa hai tập là nhỏ nhất.
- Với mỗi giá trị $x$ trong $S_1$, chặt nhị phân để tìm giá trị gần $\frac{S}{2}-x$ nhất.

Code:
:::spoiler

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;
const long long INF=2e18+5;
long long sum[5];
vector<int> t1,t2;
vector<long long> ch1,ch2;

void Btr(vector<int>& t,vector<long long>& ch,int i)
{
    for (int j=0;j<2;j++) {
        sum[j]+=t[i];
        if (i==int(t.size())-1) ch.push_back(abs(sum[0]-sum[1]));
        else Btr(t,ch,i+1);
        sum[j]-=t[i];
    }
}

int main()
{
    int n,a;
    cin>>n;
    for (int i=1;i<=int(n/2);i++) {
        cin>>a;
        t1.push_back(a);
    }
    Btr(t1,ch1,0);
    for (int i=n/2+1;i<=n;i++) {
        cin>>a;
        t2.push_back(a);
    }
    Btr(t2,ch2,0);
    sort(ch2.begin(),ch2.end());

    long long res=INF;
    for (long long i:ch1) {
        int tmp=lower_bound(ch2.begin(),ch2.end(),i)-ch2.begin();
        if (tmp==int(ch2.size())) {
            tmp--;
            res=min(res,i-ch2[tmp]);
        }
        else res=min(res,ch2[tmp]-i);
        if (tmp) res=min(res,i-ch2[tmp-1]);
        if (tmp<int(ch2.size())-1) res=min(res,ch2[tmp+1]-i);
    }
    cout<<res;
}

:::

# Gợi ý
## Bài 4: [Trộm sách](https://marisaoj.com/problem/111)
- Chia làm hai tập rồi quay lui. Với $(w, v)$ ở tập một, trong các tập con ở tập hai với cân nặng không vượt quá $S - w$, tìm giá trị $v$ lớn nhất để ghép đôi.

## Bài 5: [Tập con có tổng lớn nhất](https://marisaoj.com/problem/112)
- Cũng chia làm hai tập rồi quay lui tổng mod $10^9$. Với $x$ ở tập $S_1$, tìm giá trị $y$ ở tập $S_2$ sao cho $x+y \mod 10^9$ lớn nhất, nghĩa là gần $x+y$ với $10^9$ nhất, nhưng không được lớn hơn hoặc bằng $10^9$, nếu mà lớn hơn thì lấy luôn $x$ hoặc $y$ cho rồi.