Problem https://leetcode.com/problems/combination-sum What is the Problem? You are given a list of integers candidates. You are also given an integer target. Each number in candidates can be reused any number of times. Return all unique combinations of numbers that sum up to target. Approach Use a recursive approach with backtracking (similar to BFS) to explore all possible combinations. The base case of the recursion is when the sum of the current combination equals the target. To avoid redundant computations and duplicate combinations, sort the list first and only consider the current or later candidates in recursive calls. Solution def combinationSum(candidates: List[int], target: int) -> List[List[int]]: combinations = [] def helper(index, target, selected): if target == 0: return selected for idx in range(index, len(candidates)): candidate = candidates[idx] if target - candidate >= 0: combination = helper(idx, target - candidate, selected + [candidate]) if combination and combination not in combinations: combinations.append(combination) helper(0, target, []) return combinations assert combinationSum([2,3,6,7], 7) == [[2,2,3],[7]] Key Concepts Recursive exploration: We explore all paths by repeatedly subtracting from the target. Backtracking: We track the current path (selected) and backtrack when necessary. Avoiding duplicates: By always iterating from the current index (index), we prevent combinations with the same elements in different orders. Time Complexity Let T be the target and N be the number of candidates. In the worst case, the time complexity is exponential, approximately O(N^T), due to the branching factor of the recursive calls. Sorting the candidates first and pruning paths early can significantly reduce redundant computations. ...
Background There was a side project within our team focused on designing a new test framework that would allow others to easily add new test cases without needing to understand the underlying workings of the framework. The framework was also intended to be deployable across various platforms without requiring any toolchain setup in advance. Some compiled languages came to mind—Go in particular. Thanks to its static compilation and straightforward build process, we could deploy binaries to almost any platform in our company. It also happened to be my first project using Go, which made the experience even more exciting. ...