<commit_before>---
title: 'Backtracking'
date: 2017-07-23
permalink: /posts/2017/07/23/blog-post-2/
---

Backtracking is a general algorithm for finding all (or some) solutions to some computational problems, notably constraint satisfaction problems, that incrementally builds candidates to the solutions, and abandons each partial candidate ("backtracks") as soon as it determines that the candidate cannot possibly be completed to a valid solution.

My template for backtracking problem:

Define a helper function which includes path, res, and some constraints to be satisfied.

## 17. Letter Combinations of a Phone Number
<pre>
class Solution(object):
<commit_msg>Update 2017-07-23-blog-post-2.md<commit_after>---
title: 'Backtracking'
date: 2017-07-23
permalink: /posts/2017/07/23/blog-post-2/
---

Backtracking is a general algorithm for finding all (or some) solutions to some computational problems, notably constraint satisfaction problems, that incrementally builds candidates to the solutions, and abandons each partial candidate ("backtracks") as soon as it determines that the candidate cannot possibly be completed to a valid solution.

My template for backtracking problem: Define a helper function which mainly includes variables path (the current result), res (the set that stores the final results). When the path (the current result) satisfies some specific constraints, store it in res. Otherwise apply recursion to try new results.

## 17. Letter Combinations of a Phone Number
<pre>
class Solution(object):

{'fraction_non_alphanumeric': 0.06932635709614127, 'fraction_numerical': 0.030739045127534337, 'mean_word_length': 5.0236220472440944, 'pattern_counts': {'":': 0, '<': 5, '<?xml version=': 0, '>': 5, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '223456', 'n_tokens_mistral': 411, 'n_tokens_neox': 366, 'n_words': 198}