Permutation and Combination

Permutation & Combination

⭐ 1. Permutation (P)

• Order matters.

• Selecting and arranging items.

Formula

⭐ 2. Combination (C)

• Order does not matter.

• Only selecting items.

Formula

They are related as:

The recursive algorithm to generate all permutation of array of characters (string)

void permute(char arr[], int i, int n) {
    if(i == n){
        print(arr);
        return;
    }

    for (int j = i; j<= n; j++) {
        swap(arr[i], arr[j]);
        permute(arr, i + 1, n);
        swap(arr[i], arr[j]); // backtrack
    }
}

Recursion tree for permutation of the string "ABC"