162. 排列所有組合

Task Description
排列所有組合
給定一組長度為 n 的正整數陣列 a ，且 a 中元素不會重複。請列舉 a 的所有排列
印出排列順序規則 : 以a1, a2, a3, ... , an當作說明序列
總共有n!排序，第一項就有n種，每一種後方又有(n-1)!
所以印出時第一項由a1先印完後方的(n-1)!種後才換a2印
例如 : 輸入3 1 2
第一項有3種可能 :
數字3都放在最前方，之後有兩種，先印1 2再印2 1
數字1都放在中間，之後有兩種，先印3 2再印2 3
數字2都放在最後方，之後有兩種，先印3 1再印1 3

Hint

藉由兩個數字交換達成每項所有組合搭配遞迴。例 : 3 1 2 第一項可以跟自己和交換或跟1交換或跟2交換，再呼叫遞迴做相同事情。

permute.h

打上 function header 以及相關的設定。

#include <stdio.h> 
void permute(int* a, int l, int r, int n);

permute.c

撰寫程式碼後對應上傳。

#include "permute.h"
 
void permute(int* a, int l, int r, int n) {
    // add your code
}

main.c

這個檔案無法更改也無須上傳。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22 #include <stdio.h> 
#include <stdlib.h> 
#include "permute.h"
 
void swap(int* x, int* y) {
    int temp;
    temp = *x;
    *x = *y;
    *y = temp;
}
 
int main() {
    int n, i;
    scanf("%d", &n);
    int* a = (int*)malloc(n * sizeof(int));
    for (i = 0; i < n; i++) {
        scanf("%d", &a[i]);
    }
    permute(a, 0, n - 1, n);
    free(a);
    return 0;
}

Input Format

輸入的第一列為陣列長度 n (0<n≤9)。第二列為陣列元素數值 a[i] (0<a[i]≤1000)。

Output Format

印出所有組合，每列最後多一個空格。

Sample Input

1
2 3
1 2 3

Sample Output

Sample Input

1
2 4
1 2 3 4

Sample Output

Submit

Testdata Set