# 暴力
###### tags: `Algorithm`

## backtrack
枚舉多維度數值的方法。運用遞迴依序窮舉各個維度的數值，製作所有可能的多維度數值，並且在遞迴途中避免枚舉不正確的多維度數值。

void backtrack(int n)   // n 為現在正在枚舉的維度
{
    // it's a solution
    if (n == 5)
    {
        print_solution();
        return;
    }
 
    // 逐步枚舉數字1到10，並且遞迴下去，繼續枚舉之後的維度。
    for (int i=1; i<=10; ++i)
    {
        solution[n] = i;
        backtrack(n+1);
    }
}

### Difference Between DFS
[Backtracking](http://en.wikipedia.org/wiki/Backtracking) is a more ==general purpose algorithm==.

[Depth-First search](http://en.wikipedia.org/wiki/Depth-first_search) is a ==specific form== of backtracking related to ==searching tree structures==. From Wikipedia:

> One starts at the root (selecting some node as the root in the graph case) and explores as far as possible along each branch before backtracking.

It uses backtracking as part of its means of working with a tree, but is limited to a tree structure.

Backtracking, though, can be used on any type of structure where portions of the domain can be eliminated - whether or not it is a logical tree. The Wiki example uses a chessboard and a specific problem - you can look at a specific move, and eliminate it, then backtrack to the next possible move, eliminate it, etc.

### 枚舉排列

int solution[5];    // 用來存放一組可能的答案
bool filled[5];     // 記錄各個位置是否填過數字，填過為true
 
void backtrack(int n)
{
    // it's a solution, print it
    if (n == 5)
    {
        for (int i=0; i<5; i++)
            cout << solution[i] << ' ';
        cout << endl;
 
        return;
    }
 
    for (int i=0; i<5; i++)     // 試著將數字 n 填入各個位置
        if (!filled[i])
        {
            filled[i] = true;   // 記錄填過的位置
 
            solution[i] = n;    // 將數字 n 填入第 i 格
            backtrack(n+1);     // 繼續枚舉下一個數字
 
            filled[i] = false;  // 回收位置
        }
}
 
void enumerate_permutations()
{
    for (int i=0; i<5; i++) // initialization
        filled[i] = false;
 
    backtrack(0);   // 印出數字1到5的所有排列。
}

### 數字排列

#include<bits/stdc++.h>
using namespace std;
#define rep( i, a, b) for( int i=(a); i<(b); i++)
#define exist(m,k) ( m.find(k) != m.end())
#define info( nm, i) cout << ":::INFO: " << nm << ": " << i << '\n'; 

#define maxN 100

vector<int> nums{ 1,1,1,12};
map< int, int> amnts;
vector<int> p;

void print_p(int n){
    if( n==nums.size()){
        rep( i, 0, n) cout << p[i] << ' ';
        cout << '\n';
        return;
    }

    for( auto &kvp: amnts){
        if( kvp.second > 0){
            p[n] = kvp.first;
            kvp.second--;
            print_p( n+1);
            kvp.second++;
        }
    }
}

int main(){
    p.resize( maxN);
    for( auto x: nums){ // get amount of elements
        if( !exist( amnts, x)) amnts[x] = 0;
        amnts[x]++;
    }
    print_p(0);
}

## 0/1 枚舉

void Enumerate(int arr[],int n){
    for(int x=(1<<n)−1;x>=0;−−x)
        for(int i=0,t=x;i<n;++i,t/=2)
            if(t&1) //use a[i]
}

[https://stackoverflow.com/questions/1294720/whats-the-difference-between-backtracking-and-depth-first-search](https://stackoverflow.com/questions/1294720/whats-the-difference-between-backtracking-and-depth-first-search)
[http://www.csie.ntnu.edu.tw/~u91029/Backtracking.html](http://www.csie.ntnu.edu.tw/~u91029/Backtracking.html)