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.

1 | s = "123" |

- 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

### Code

1 | public class StringPermutation { |

ref: https://www.geeksforgeeks.org/write-a-c-program-to-print-all-permutations-of-a-given-string/

### Alternative approach for string permutation

- instead of swapping, we can also add additional space
`boolean[] used`

to record character already been used

1 | class Solution { |

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

1 | import java.util.ArrayList; |

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

### Alternative approach w/ backtracking

1 | // 1ms version... |

1 | // 35ms version... |

References

front cover ref: https://www.geeksforgeeks.org/write-a-c-program-to-print-all-permutations-of-a-given-string/

## log

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