# Đệ quy
## Sinh tập hợp con
Dưới đây là ứng dụng của đệ quy trong việc sinh tập hợp con.

void gen(int k){
    if (k==n+1){
        // process subset
    }
    else{
        subset.push_back(k);
        gen(k+1);
        subset.pop_back();
        gen(k+1);
    }
}

Độ phức tạp: $O(2^N)$.
## Sinh hoán vị
Tiếp theo là cách sinh các hoán vị.

void gen(){
    if (perm.size()==n){
        // process permutation
    }
    else{
        for (int i=1;i<=n;i++){
            if (chosen[i]){
                continue;
            }   
            chosen[i]=true;
            perm.push_back(i);
            gen();
            chosen[i]=false;
            perm.pop_back();
        }
    }
}

Độ phức tạp: $O(!N)$.
## Quay lui
Quay lui bắt đầu với không lời giải sau đó mở rộng nó ra dần. Quay lui sẽ duyệt qua tất cả các phương án giải.
### Bài toán N Quân Hậu
Cho một bàn cờ $n$ x $n$ với $n$ quân hậu. Hỏi có bao nhiêu cách sắp xếp các quân hậu trên bàn cờ sao cho không có hai quân hậu nào tấn công nhau?

void queen(int y){
    if (y==n){
        ans++;
        return;
    }
    for (int x=0;x<n;x++){
        if (col[x]||diag1[x+y]||diag2[x-y+n-1]){
            continue;
        }
        col[x]=diag1[x+y]=diag2[x-y+n-1]=1;
        queen(y+1);
        col[x]=diag1[x+y]=diag2[x-y+n-1]=0;
    }
}

Độ phức tạp: $O(!N)$.