prompt: We are currently solving the following issue within our repository. Here is the issue text:
  --- BEGIN ISSUE ---
  Improve our test coverage
  ### Feature description
  
  Many of our existing algorithm files have little to no unit testing. This is problematic because this can easily let bugs slip through. We want some assurance that the code we currently have is correct and functional. We welcome all contributors to open PRs to help us add tests to our codebase.
  
  ### How to find low-coverage files
  
  Go to the Actions tab in this repository and find the most recent **build** workflow run. Open the logs under "Run Tests" and scroll down until you find the section on code coverage:
  ```
  ---------- coverage: platform linux, python 3.12.0-final-0 -----------
  Name                                                                          Stmts   Miss  Cover   Missing
  -----------------------------------------------------------------------------------------------------------
  quantum/q_fourier_transform.py                                                   30     30     0%   14-93
  scripts/validate_solutions.py                                                    54     54     0%   2-94
  strings/min_cost_string_conversion.py                                            78     75     4%   20-57, 61-75, 79-129
  ...
  ```
  The "Cover" column tells you what percentage of the lines in that file are covered by tests. We want to increase this percentage for existing files. Find a file with low coverage percentage that you wish to write tests for, add doctests for each function, and open a PR with your changes. You do not need to have a perfect coverage percentage, but all functions should have doctests.
  
  Some files will naturally be hard to write tests for. For example, the file may be poorly written because they lack any functions. Other files might be how-tos, meaning they simply demonstrate how to use an existing library's functions rather than implementing the algorithm themselves. Ignore these kinds of files, as they will need to be rewritten eventually. Furthermore, ignore files in the `web_programming` and `project_euler` directories. Web programming files are inherently hard to test and Project Euler files have their own validation workflow, so don't worry about their test coverage.
  
  _**When you open your PR, put "Contributes to #9943" in the PR description.**_ Do not use the word "fixes", "resolves", or "closes". This issue is an ongoing one, and your PR will not single-handedly resolve this issue.
  
  ### How to add doctests
  
  A doctest is a unit test that is contained within the documentation comment (docstring) for a function. Here is an example of what doctests look like within a docstring:
  ```py
  def add(a: int, b: int) -> int:
      """
      Adds two non-negative numbers.
      >>> add(1, 1)
      2
      >>> add(2, 5)
      7
      >>> add(1, 0)
      1
      >>> add(-1, -1)
      Traceback (most recent last):
      ...
      ValueError: Numbers must be non-negative
      """
  ```
  For every function in the file you choose, you should write doctests like the ones shown above in its docstring. If a function doesn't have a docstring, add one. Your doctests should be comprehensive but not excessive: you should write just enough tests to cover all basic cases as well as all edge cases (e.g., negative numbers, empty lists, etc).
  
  Do not simply run a function on some example inputs and put its output as the expected output for a doctest. This assumes that the function is implemented correctly when it might not be. Verify independently that your doctests and their expected outputs are correct. **Your PR will not be merged if it has failing tests.** If you happen to discover a bug while writing doctests, please fix it.
  
  _**Please read our [contributing guidelines](https://github.com/TheAlgorithms/Python/blob/master/CONTRIBUTING.md) before you contribute.**_
  
  --- END ISSUE ---
  
  Below are some code segments, each from a relevant file. One or more of these files may contain bugs.
  --- BEGIN FILES ---
  Path: `backtracking/all_combinations.py`
  Content:
  ```
  1 """
  2         In this problem, we want to determine all possible combinations of k
  3         numbers out of 1 ... n. We use backtracking to solve this problem.
  4         Time complexity: O(C(n,k)) which is O(n choose k) = O((n!/(k! * (n - k)!)))
  5 """
  6 from __future__ import annotations
  7 
  8 
  9 def generate_all_combinations(n: int, k: int) -> list[list[int]]:
  10     """
  11     >>> generate_all_combinations(n=4, k=2)
  12     [[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]
  13     """
  14 
  15     result: list[list[int]] = []
  16     create_all_state(1, n, k, [], result)
  17     return result
  18 
  19 
  20 def create_all_state(
  21     increment: int,
  22     total_number: int,
  23     level: int,
  24     current_list: list[int],
  25     total_list: list[list[int]],
  26 ) -> None:
  27     if level == 0:
  28         total_list.append(current_list[:])
  29         return
  30 
  31     for i in range(increment, total_number - level + 2):
  32         current_list.append(i)
  33         create_all_state(i + 1, total_number, level - 1, current_list, total_list)
  34         current_list.pop()
  35 
  36 
  37 def print_all_state(total_list: list[list[int]]) -> None:
  38     for i in total_list:
  39         print(*i)
  40 
  41 
  42 if __name__ == "__main__":
  43     n = 4
  44     k = 2
  45     total_list = generate_all_combinations(n, k)
  46     print_all_state(total_list)
  47
  ```
  --- END FILES ---
  
  Please first localize the bug based on the issue statement, and then generate a patch according to the `git diff` format fenced by three backticks.
  
  Here is an example:
  
  ```diff
  diff --git a/examples/server_async.py b/examples/server_async.py
  --- a/examples/server_async.py
  +++ b/examples/server_async.py
  @@ -313,4 +313,4 @@
   
   
   if __name__ == "__main__":
  -    asyncio.run(run_async_server("."), debug=True)
  +    asyncio.run(run_async_server(), debug=True)
  diff --git a/examples/server_sync.py b/examples/server_sync.py
  --- a/examples/server_sync.py
  +++ b/examples/server_sync.py
  @@ -313,5 +313,5 @@
   
   
   if __name__ == "__main__":
  -    server = run_sync_server(".")
  +    server = run_sync_server()
       server.shutdown()
  
  ```
  
golden_diff: diff --git a/backtracking/all_combinations.py b/backtracking/all_combinations.py
  --- a/backtracking/all_combinations.py
  +++ b/backtracking/all_combinations.py
  @@ -1,15 +1,40 @@
   """
           In this problem, we want to determine all possible combinations of k
           numbers out of 1 ... n. We use backtracking to solve this problem.
  -        Time complexity: O(C(n,k)) which is O(n choose k) = O((n!/(k! * (n - k)!)))
  +
  +        Time complexity: O(C(n,k)) which is O(n choose k) = O((n!/(k! * (n - k)!))),
   """
   from __future__ import annotations
   
  +from itertools import combinations
  +
  +
  +def combination_lists(n: int, k: int) -> list[list[int]]:
  +    """
  +    >>> combination_lists(n=4, k=2)
  +    [[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]
  +    """
  +    return [list(x) for x in combinations(range(1, n + 1), k)]
  +
   
   def generate_all_combinations(n: int, k: int) -> list[list[int]]:
       """
       >>> generate_all_combinations(n=4, k=2)
       [[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]
  +    >>> generate_all_combinations(n=0, k=0)
  +    [[]]
  +    >>> generate_all_combinations(n=10, k=-1)
  +    Traceback (most recent call last):
  +        ...
  +    RecursionError: maximum recursion depth exceeded
  +    >>> generate_all_combinations(n=-1, k=10)
  +    []
  +    >>> generate_all_combinations(n=5, k=4)
  +    [[1, 2, 3, 4], [1, 2, 3, 5], [1, 2, 4, 5], [1, 3, 4, 5], [2, 3, 4, 5]]
  +    >>> from itertools import combinations
  +    >>> all(generate_all_combinations(n, k) == combination_lists(n, k)
  +    ...     for n in range(1, 6) for k in range(1, 6))
  +    True
       """
   
       result: list[list[int]] = []
  @@ -34,13 +59,17 @@
           current_list.pop()
   
   
  -def print_all_state(total_list: list[list[int]]) -> None:
  -    for i in total_list:
  -        print(*i)
  +if __name__ == "__main__":
  +    from doctest import testmod
   
  +    testmod()
  +    print(generate_all_combinations(n=4, k=2))
  +    tests = ((n, k) for n in range(1, 5) for k in range(1, 5))
  +    for n, k in tests:
  +        print(n, k, generate_all_combinations(n, k) == combination_lists(n, k))
   
  -if __name__ == "__main__":
  -    n = 4
  -    k = 2
  -    total_list = generate_all_combinations(n, k)
  -    print_all_state(total_list)
  +    print("Benchmark:")
  +    from timeit import timeit
  +
  +    for func in ("combination_lists", "generate_all_combinations"):
  +        print(f"{func:>25}(): {timeit(f'{func}(n=4, k = 2)', globals=globals())}")
  
verification_info: {"golden_diff": "diff --git a/backtracking/all_combinations.py b/backtracking/all_combinations.py\n--- a/backtracking/all_combinations.py\n+++ b/backtracking/all_combinations.py\n@@ -1,15 +1,40 @@\n \"\"\"\n         In this problem, we want to determine all possible combinations of k\n         numbers out of 1 ... n. We use backtracking to solve this problem.\n-        Time complexity: O(C(n,k)) which is O(n choose k) = O((n!/(k! * (n - k)!)))\n+\n+        Time complexity: O(C(n,k)) which is O(n choose k) = O((n!/(k! * (n - k)!))),\n \"\"\"\n from __future__ import annotations\n \n+from itertools import combinations\n+\n+\n+def combination_lists(n: int, k: int) -> list[list[int]]:\n+    \"\"\"\n+    >>> combination_lists(n=4, k=2)\n+    [[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]\n+    \"\"\"\n+    return [list(x) for x in combinations(range(1, n + 1), k)]\n+\n \n def generate_all_combinations(n: int, k: int) -> list[list[int]]:\n     \"\"\"\n     >>> generate_all_combinations(n=4, k=2)\n     [[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]\n+    >>> generate_all_combinations(n=0, k=0)\n+    [[]]\n+    >>> generate_all_combinations(n=10, k=-1)\n+    Traceback (most recent call last):\n+        ...\n+    RecursionError: maximum recursion depth exceeded\n+    >>> generate_all_combinations(n=-1, k=10)\n+    []\n+    >>> generate_all_combinations(n=5, k=4)\n+    [[1, 2, 3, 4], [1, 2, 3, 5], [1, 2, 4, 5], [1, 3, 4, 5], [2, 3, 4, 5]]\n+    >>> from itertools import combinations\n+    >>> all(generate_all_combinations(n, k) == combination_lists(n, k)\n+    ...     for n in range(1, 6) for k in range(1, 6))\n+    True\n     \"\"\"\n \n     result: list[list[int]] = []\n@@ -34,13 +59,17 @@\n         current_list.pop()\n \n \n-def print_all_state(total_list: list[list[int]]) -> None:\n-    for i in total_list:\n-        print(*i)\n+if __name__ == \"__main__\":\n+    from doctest import testmod\n \n+    testmod()\n+    print(generate_all_combinations(n=4, k=2))\n+    tests = ((n, k) for n in range(1, 5) for k in range(1, 5))\n+    for n, k in tests:\n+        print(n, k, generate_all_combinations(n, k) == combination_lists(n, k))\n \n-if __name__ == \"__main__\":\n-    n = 4\n-    k = 2\n-    total_list = generate_all_combinations(n, k)\n-    print_all_state(total_list)\n+    print(\"Benchmark:\")\n+    from timeit import timeit\n+\n+    for func in (\"combination_lists\", \"generate_all_combinations\"):\n+        print(f\"{func:>25}(): {timeit(f'{func}(n=4, k = 2)', globals=globals())}\")\n", "issue": "Improve our test coverage\n### Feature description\r\n\r\nMany of our existing algorithm files have little to no unit testing. This is problematic because this can easily let bugs slip through. We want some assurance that the code we currently have is correct and functional. We welcome all contributors to open PRs to help us add tests to our codebase.\r\n\r\n### How to find low-coverage files\r\n\r\nGo to the Actions tab in this repository and find the most recent **build** workflow run. Open the logs under \"Run Tests\" and scroll down until you find the section on code coverage:\r\n```\r\n---------- coverage: platform linux, python 3.12.0-final-0 -----------\r\nName                                                                          Stmts   Miss  Cover   Missing\r\n-----------------------------------------------------------------------------------------------------------\r\nquantum/q_fourier_transform.py                                                   30     30     0%   14-93\r\nscripts/validate_solutions.py                                                    54     54     0%   2-94\r\nstrings/min_cost_string_conversion.py                                            78     75     4%   20-57, 61-75, 79-129\r\n...\r\n```\r\nThe \"Cover\" column tells you what percentage of the lines in that file are covered by tests. We want to increase this percentage for existing files. Find a file with low coverage percentage that you wish to write tests for, add doctests for each function, and open a PR with your changes. You do not need to have a perfect coverage percentage, but all functions should have doctests.\r\n\r\nSome files will naturally be hard to write tests for. For example, the file may be poorly written because they lack any functions. Other files might be how-tos, meaning they simply demonstrate how to use an existing library's functions rather than implementing the algorithm themselves. Ignore these kinds of files, as they will need to be rewritten eventually. Furthermore, ignore files in the `web_programming` and `project_euler` directories. Web programming files are inherently hard to test and Project Euler files have their own validation workflow, so don't worry about their test coverage.\r\n\r\n_**When you open your PR, put \"Contributes to #9943\" in the PR description.**_ Do not use the word \"fixes\", \"resolves\", or \"closes\". This issue is an ongoing one, and your PR will not single-handedly resolve this issue.\r\n\r\n### How to add doctests\r\n\r\nA doctest is a unit test that is contained within the documentation comment (docstring) for a function. Here is an example of what doctests look like within a docstring:\r\n```py\r\ndef add(a: int, b: int) -> int:\r\n    \"\"\"\r\n    Adds two non-negative numbers.\r\n    >>> add(1, 1)\r\n    2\r\n    >>> add(2, 5)\r\n    7\r\n    >>> add(1, 0)\r\n    1\r\n    >>> add(-1, -1)\r\n    Traceback (most recent last):\r\n    ...\r\n    ValueError: Numbers must be non-negative\r\n    \"\"\"\r\n```\r\nFor every function in the file you choose, you should write doctests like the ones shown above in its docstring. If a function doesn't have a docstring, add one. Your doctests should be comprehensive but not excessive: you should write just enough tests to cover all basic cases as well as all edge cases (e.g., negative numbers, empty lists, etc).\r\n\r\nDo not simply run a function on some example inputs and put its output as the expected output for a doctest. This assumes that the function is implemented correctly when it might not be. Verify independently that your doctests and their expected outputs are correct. **Your PR will not be merged if it has failing tests.** If you happen to discover a bug while writing doctests, please fix it.\r\n\r\n_**Please read our [contributing guidelines](https://github.com/TheAlgorithms/Python/blob/master/CONTRIBUTING.md) before you contribute.**_\n", "before_files": [{"content": "\"\"\"\n        In this problem, we want to determine all possible combinations of k\n        numbers out of 1 ... n. We use backtracking to solve this problem.\n        Time complexity: O(C(n,k)) which is O(n choose k) = O((n!/(k! * (n - k)!)))\n\"\"\"\nfrom __future__ import annotations\n\n\ndef generate_all_combinations(n: int, k: int) -> list[list[int]]:\n    \"\"\"\n    >>> generate_all_combinations(n=4, k=2)\n    [[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]\n    \"\"\"\n\n    result: list[list[int]] = []\n    create_all_state(1, n, k, [], result)\n    return result\n\n\ndef create_all_state(\n    increment: int,\n    total_number: int,\n    level: int,\n    current_list: list[int],\n    total_list: list[list[int]],\n) -> None:\n    if level == 0:\n        total_list.append(current_list[:])\n        return\n\n    for i in range(increment, total_number - level + 2):\n        current_list.append(i)\n        create_all_state(i + 1, total_number, level - 1, current_list, total_list)\n        current_list.pop()\n\n\ndef print_all_state(total_list: list[list[int]]) -> None:\n    for i in total_list:\n        print(*i)\n\n\nif __name__ == \"__main__\":\n    n = 4\n    k = 2\n    total_list = generate_all_combinations(n, k)\n    print_all_state(total_list)\n", "path": "backtracking/all_combinations.py"}], "after_files": [{"content": "\"\"\"\n        In this problem, we want to determine all possible combinations of k\n        numbers out of 1 ... n. We use backtracking to solve this problem.\n\n        Time complexity: O(C(n,k)) which is O(n choose k) = O((n!/(k! * (n - k)!))),\n\"\"\"\nfrom __future__ import annotations\n\nfrom itertools import combinations\n\n\ndef combination_lists(n: int, k: int) -> list[list[int]]:\n    \"\"\"\n    >>> combination_lists(n=4, k=2)\n    [[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]\n    \"\"\"\n    return [list(x) for x in combinations(range(1, n + 1), k)]\n\n\ndef generate_all_combinations(n: int, k: int) -> list[list[int]]:\n    \"\"\"\n    >>> generate_all_combinations(n=4, k=2)\n    [[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]\n    >>> generate_all_combinations(n=0, k=0)\n    [[]]\n    >>> generate_all_combinations(n=10, k=-1)\n    Traceback (most recent call last):\n        ...\n    RecursionError: maximum recursion depth exceeded\n    >>> generate_all_combinations(n=-1, k=10)\n    []\n    >>> generate_all_combinations(n=5, k=4)\n    [[1, 2, 3, 4], [1, 2, 3, 5], [1, 2, 4, 5], [1, 3, 4, 5], [2, 3, 4, 5]]\n    >>> from itertools import combinations\n    >>> all(generate_all_combinations(n, k) == combination_lists(n, k)\n    ...     for n in range(1, 6) for k in range(1, 6))\n    True\n    \"\"\"\n\n    result: list[list[int]] = []\n    create_all_state(1, n, k, [], result)\n    return result\n\n\ndef create_all_state(\n    increment: int,\n    total_number: int,\n    level: int,\n    current_list: list[int],\n    total_list: list[list[int]],\n) -> None:\n    if level == 0:\n        total_list.append(current_list[:])\n        return\n\n    for i in range(increment, total_number - level + 2):\n        current_list.append(i)\n        create_all_state(i + 1, total_number, level - 1, current_list, total_list)\n        current_list.pop()\n\n\nif __name__ == \"__main__\":\n    from doctest import testmod\n\n    testmod()\n    print(generate_all_combinations(n=4, k=2))\n    tests = ((n, k) for n in range(1, 5) for k in range(1, 5))\n    for n, k in tests:\n        print(n, k, generate_all_combinations(n, k) == combination_lists(n, k))\n\n    print(\"Benchmark:\")\n    from timeit import timeit\n\n    for func in (\"combination_lists\", \"generate_all_combinations\"):\n        print(f\"{func:>25}(): {timeit(f'{func}(n=4, k = 2)', globals=globals())}\")\n", "path": "backtracking/all_combinations.py"}]}