---
# System prepended metadata

title: Brute-Force
tags: [' note', 109_FDCS]

---

---
tags: 109_FDCS, note
---

# Brute-Force


## 概念
暴搜的概念很簡單，窮舉每種可能的結果再判斷正確性
對，沒錯，就是遞迴

那是要遞迴甚麼東西呢
對，沒錯，就是狀態

就像是你玩遊戲時會去想下一個可能的狀態是甚麼，例如這樣
![](https://i.imgur.com/PJOew3L.png =500x)

而遞迴過程中會遇到已經確定結束的可能，這時我們就不需用繼續遞迴這個狀態下去，這種操作稱為剪枝
詳細內容可以看下面網站
[演算法筆記 - backtracking](http://web.ntnu.edu.tw/~algo/Backtracking.html)

## 講解
[DJ a343](http://203.64.191.163/ShowProblem?problemid=a343)
:::spoiler {state=open} code
```cpp!
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
constexpr int maxn = 10;
int arr[maxn], n, m;
vector<int> ans;
vector<bool> used;

void permutation(int cnt) {
    if(cnt == m) {
        for(auto& x : ans)
            cout << x << " ";
        cout << '\n';
        return;
    }
    for(int i = 0; i < n; ++i) {
        if(!used[i]) {
            ans.push_back(arr[i]);
            used[i] = true;
            permutation(cnt + 1);
            ans.pop_back();
            used[i] = false;
        }
    }
}

int main() {
    cin.tie(0), ios::sync_with_stdio(false);
    while(cin >> n >> m) {
        for(int i = 0; i < n; ++i) 
            cin >> arr[i];
        ans.clear();
        used.assign(n, 0);
        sort(arr, arr + n);
        permutation(0);
    }
    return 0;
}
```
:::

## 練習題
- [ZJ a144](https://zerojudge.tw/ShowProblem?problemid=a144)
- [ZJ a229](https://zerojudge.tw/ShowProblem?problemid=a229)
- [ZJ d757](https://zerojudge.tw/ShowProblem?problemid=d757)
- [ZJ c145](https://zerojudge.tw/ShowProblem?problemid=c145)
