## Description

Permutation and combination is very important topics in probablity, while many of the programming challenges also involved ability to generate all possible permtuation/combination for a given string. Hence, knowing how to write code to generate permutation and combination of a given string is essential.

## Permutation

Permutation of string String str = "123".

### Complexity

• $O(n!)$
• for string 123, first char has 3 choices, second char has 2 choices, etc
• hence, there are $3 x 2 x 1 = 3!$ choices in total

### Key Ideas

• result of permutation has same length as the original string
• fix one char at a time, recursively generate the rest (in circle)
• which char to fix? here is an algorithm using swap to choose char for current char index.
• ex. fix first char (curr=1) could either be one of the 1,2,3. Hence, recursion tree spans into three nodes.
• for fix second char (curr=2) with either 2,3. Since we only have two choices, hence, it spans into two nodes.
• currentIdx == string.length() - 1 indicates the end of permutation and return

### Alternative approach for string permutation

• instead of swapping, we can also add additional space boolean[] used to record character already been used

https://leetcode.com/problems/permutations/description/

CS 106B Lecture: Backtracking (permute a string): https://www.youtube.com/watch?v=78t_yHuGg-0

## Combination

### Complexity

• $O(2^n)$, where $n$ is the size of elements
• for list of 1,2,3,4,5, where k = 3. for each of the element, it could either be choosen (1), or not choosen (0).
• each element has two choices, where there are total n elemnts, hence, $O(2^n)$ total combinations
• we need one more pass $O(2^n)$ to further eliminate invalid combinations, which its size is not k

### Key Ideas

• combination problem usually asks to select n from k, where n <= k.
• similiarly to permutation, we could break big problem into smaller pieces.
• fix first charactor, then recursively solve the rest (in circle).
• which char to fix?

If a given string is s = "1234", where s.length() = 4, and k = 3. The only chars we could choose to fix is 1 and 2 since k = 3, which means we could not go beyond "2". Similary, the subproblem, w/ smaller size could be solved with the same logic, where result of combination locates at leave nodes.

### Code

LeetCode77: Combinations https://leetcode.com/problems/combinations/description/

## log

• 05/12/2019: add combination 1ms version