# Backtracking

## What is backtracking

Backtracking is an algorithmic technique for solving problems recursively by trying to build a solution incrementally, one piece at a time, removing those solutions that fail to satisfy the constraints of the problem at any point in time (by time, here, is referred to the time elapsed till reaching any level of the search tree). Backtracking can also be said as an improvement to the brute force approach. So basically, the idea behind the backtracking technique is that it searches for a solution to a problem among all the available options.

## [Leetcode 17] Letter Combinations of a Phone Number

Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. Return the answer in any order.

A mapping of digits to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.

Example 1:

1 | Input: digits = "23" |

Example 2:

1 | Input: digits = "" |

Example 3:

1 | Input: digits = "2" |

Constraints:

- 0 <= digits.length <= 4
- digits[i] is a digit in the range [‘2’, ‘9’].

Solution:

1 | class Solution: |

## [Leetcode 216] Combination Sum III

Find all valid combinations of k numbers that sum up to n such that the following conditions are true:

Only numbers 1 through 9 are used.

Each number is used at most once.

Return a list of all possible valid combinations. The list must not contain the same combination twice, and the combinations may be returned in any order.

Example 1:

1 | Input: k = 3, n = 7 |

Example 2:

1 | Input: k = 3, n = 9 |

Constraints:

- 2 <= k <= 9
- 1 <= n <= 60

1 | class Solution: |

## [Leetcode 526] Beautiful Arrangement

Suppose you have n integers labeled 1 through n. A permutation of those n integers perm (1-indexed) is considered a beautiful arrangement if for every i (1 <= i <= n), either of the following is true:

- perm[i] is divisible by i.
- i is divisible by perm[i].

Given an integer n, return the number of the beautiful arrangements that you can construct.

Example 1:

1 | Input: n = 2 |

Example 2:

1 | Input: n = 1 |

Constraints:

- 1 <= n <= 15

Solution:

1 | class Solution: |