# 遞迴的應用

## Permutation 排列
給n個相異的數字，其排列的方法數為$n!$

// chosen[i] == 1 -> i 被選過了
// chosen[i] == 0 -> i 沒被選過了
int chosen[] = {};
int queue[] = {};

int permutation(int n, int x) {
    // n個人排隊，已經排好x個
    if(n == x) {
        for(int i=1;i<=n;++i)
            cout << queue[i] << " ";
        cout << endl;
        return;
    }
    else {
        for(int i=1;i<=n;++i) {
            if(chosen[i] != 1) {
                queue[x+1] = i;
                chosen[i] = 1;
                permutation(n, x+1);
                chosen[i] = 0;
            }
        }
    }
}

int main() {
    permutation(5, 0);
}

### Exercise
http://www.tcgs.tc.edu.tw:1218/ShowProblem?problemid=b038

## Choose $k$ out of $n$ （作業）

Exampe: $n=4$ and $k=2$
Then you should output

1 2
1 3
1 4
2 3
2 4
3 4

作法

int ans[10];
void choose(int n, int i, int k, int x) {
    // k 是目標選幾個
    // x 是目前選幾個
    // n 是總共有幾個數字
    // i 是目前看第幾個數字
    if(k == x || i == n+1) {
        if(k == x) {
            for(int j=0;j<k;++j) {
                cout << ans[j] << " ";
            }
            cout << endl;
        }
        return;
    }
    else {
        // 先選
        ans[x] = i;
        choose(n, i+1, k, x+1);
        // 再不選
        choose(n, i+1, k, x);
    }
}

## Brute-force $2^n$ possibilities

### Exercise
http://infor.ylsh.ilc.edu.tw/JudgeOnline/problem.php?id=1027

int solve(int n, int i, int sum) {
    // i 是目前看第幾個數字
    // n 是總共有幾個數字
    // sum 是已選的數字的總和
}