Hi, Folks! Today, I solved three problems on LeetCode: Combination Sum, Combination Sum II, and Partition Equal Subset Sum. For the first two problems, we use backtracking to find all the possible solutions. When the task is to explore all possible solutions, backtracking is often the preferred approach. Typically, in problems, we stop once we find a solution, but in backtracking, we must undo our choices and explore other possible solutions. The process of undoing choices and continuing the search is what we refer to as backtracking.
Backtracking is an important concept that can solve many difficult problems efficiently, such as N-Queens, Word Search, and Combination Sum, among others.
To solve the Partition Equal Subset Sum problem, we use dynamic programming rather than a hash map. We track whether it’s possible to form a subset with a given sum. It’s somewhat similar to a real-life scenario where you go grocery shopping and use a checklist to ensure you buy every required item. You mark off each item after purchase. Similarly, in dynamic programming, we mark the achievable subset sums as we process each element in the array.
I hope my experience will be helpful!
Top comments (0)