GeezerVisonThe World Wide Web, restored to 800 pixels of glory. |
| Home|About|Gaming cabinet|Archives|How it works|Starter sites |
GeezerVison is showing github.com — Python-1/backtracking/combination_sum.py at master · https-github-com-nzysoft/Python-1 Expand file tree/ Copy pathcombination_sum.pyMore file actions 66 lines (54 loc) · 1.89 KB / Copy pathcombination_sum.pyFile metadata and controls66 lines (54 loc) · 1.89 KB 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 """ In the Combination Sum problem, we are given a list consisting of distinct integers. We need to find all the combinations whose sum equals to target given. We can use an element more than one. Time complexity(Average Case): O(n!) Constraints: 1 <= candidates.length <= 30 2 <= candidates[i] <= 40 All elements of candidates are distinct. 1 <= target <= 40 """ def backtrack( candidates: list, path: list, answer: list, target: int, previous_index: int ) -> None: """ A recursive function that searches for possible combinations. Backtracks in case of a bigger current combination value than the target value. Parameters ---------- previous_index: Last index from the previous search target: The value we need to obtain by summing our integers in the path list. answer: A list of possible combinations path: Current combination candidates: A list of integers we can use. """ if target == 0: answer.append(path.copy()) else: for index in range(previous_index, len(candidates)): if target >= candidates[index]: path.append(candidates[index]) backtrack(candidates, path, answer, target - candidates[index], index) path.pop(len(path) - 1) def combination_sum(candidates: list, target: int) -> list: """ >>> combination_sum([2, 3, 5], 8) [[2, 2, 2, 2], [2, 3, 3], [3, 5]] >>> combination_sum([2, 3, 6, 7], 7) [[2, 2, 3], [7]] >>> combination_sum([-8, 2.3, 0], 1) Traceback (most recent call last): ... RecursionError: maximum recursion depth exceeded in comparison """ path = [] # type: list[int] answer = [] # type: list[int] backtrack(candidates, path, answer, target, 0) return answer def main() -> None: print(combination_sum([-8, 2.3, 0], 1)) if __name__ == "__main__": import doctest doctest.testmod() main() |
| You are visitor 01402520 — GeezerVison does not store the pages you look up. Best viewed with Netscape Navigator 4.7 or Internet Explorer 6 at 800×600. No cookies required. |