39_combination_sum

dz / leetcode / 39_combination_sum

Summary

Given an array of distinct integers candidates and a target integer target, return a list of all unique combinations of candidates where the chosen numbers sum to target. You may return the combinations in any order. The same number may be chosen from candidates an unlimited number of times. Two combinations are unique if the frequency of at least one of the chosen numbers is different. The test cases are generated such that the number of unique combinations that sum up to target is less than 150 combinations for the given input.

Node Tree

• intuition
  • handling_distinction
    • select_candidates_in_order
  • intuition_basically_correct
  • dynamic_programming
    • handling_distinction
      • select_candidates_in_order
    • use_of_remainder
    • approach_1_backtracking
      • intuition_basically_correct
      • select_candidates_in_order
      • space_complexity
      • time_complexity
        • space_complexity
      • visualized_using_graph
      • backtracking
        • backtracking_wiki
      • combo_sum_3
      • depth_first_traversal
        • often_implemented_recursively
  • eliminate_args_greater
• URL
• editorial
  • approach_1_backtracking
    • intuition_basically_correct
    • select_candidates_in_order
    • space_complexity
    • time_complexity
      • space_complexity
    • visualized_using_graph
    • backtracking
      • backtracking_wiki
    • combo_sum_3
    • depth_first_traversal
      • often_implemented_recursively

Nodes

URL
content	URL
hyperlink	https://leetcode.com/problems/combination-sum/

intuition
content	One of those problems where I feel like a brute-force solution would be enormously inefficient. Fortunately the bounds are pretty small.
children	handling_distinction, intuition_basically_correct (basically correct intuition), dynamic_programming, eliminate_args_greater

eliminate_args_greater
content	Any number greater than the target is eliminated.
parents	intuition

dynamic_programming
content	This is probably a dynamic programming slash recursive backtracking solution. You can always break down a problem into "given an initial value X, find all the numbers that can add to less than or equal to target". Repeat that recursively, and keep track of numbers so far. Recursion ends when there is no number that can be less than or equal to target. Add to list if it is exactly the target. If sum is less than target, recurse.
children	handling_distinction, use_of_remainder (My logic was slightly different, opting to keep the current,sum rather than remainder.), approach_1_backtracking (I also mentioned "backtracking" here, which is probably,closer to what it actually is)
parents	intuition

handling_distinction
content	In past problems, there have been solutions that have really elegantly handled distinctness. I forget them now. Perhaps it's how you set up the iteration for finding the numbers. When you check for matching sums, you're going through each number once. I'm willing to believe that ordering prevents duplicates from happening.
children	select_candidates_in_order (My hunch about doing things in order was correct)
parents	dynamic_programming, intuition

editorial
content	editorial
children	approach_1_backtracking

approach_1_backtracking
content	Approach 1: backtracking
children	intuition_basically_correct, select_candidates_in_order, space_complexity, time_complexity, visualized_using_graph, backtracking (definition), combo_sum_3, depth_first_traversal
parents	editorial, dynamic_programming

combo_sum_3
content	Combination sum iii: recommended to solve before continuing. has a very similar solution, and is slightly easier
parents	approach_1_backtracking
remarks	I am not tackling this problem today
hyperlink	https://leetcode.com/problems/combination-sum-iii/description/

backtracking
content	Backtracking is a general algorithm for finding all (or some) solutions to some computational problems. The idea is that it incrementally builds candidates to the solutions, and abandons a candidate ("backtrack") as soon as it determines that this candidate is not a final solution.
children	backtracking_wiki
parents	approach_1_backtracking

backtracking_wiki
content	Backtracking Wikipedia page
parents	backtracking
hyperlink	https://en.wikipedia.org/wiki/Backtracking

visualized_using_graph
content	Can be visualized using graph (tree?). At any instance, can be at only one of the nodes.
parents	approach_1_backtracking

select_candidates_in_order
content	An important detail on choosing the next number is that they are selected in order, where the total candidates are a list. Once a candidate is added to the current combination, there is no looking back at the previous candidates in the next explorations.
parents	handling_distinction, approach_1_backtracking

depth_first_traversal
content	The backtracking algorithm is unfolded as Depth-First Tree Traversal, or DFS.
children	often_implemented_recursively
parents	approach_1_backtracking

often_implemented_recursively
content	Often implemented with recursion
parents	depth_first_traversal

use_of_remainder
content	Use of remainder variable to keep track of how much to the target is remaining. Base case remain==0 means a combination has been found, remain < 0 means value has been exceeded and exploration ceases.
parents	dynamic_programming

time_complexity
content	O(N^(T/M + 1)) where N is number of candidates, T is target value, and M is the minimal value among the candidates.
children	space_complexity (related)
parents	approach_1_backtracking
remarks	not sure how this was derived, but this was an interestingly precise O number.

space_complexity
content	O(T/M)
parents	approach_1_backtracking, time_complexity
remarks	similar to the time complexity, very specific. Not sure how it was derived.

intuition_basically_correct
content	I think my intuition for this one was basically correct for this, though I thought the solution was an example of dynamic programming, not backtracking, even though I wrote down both. there's clearly a bunch of algorithms that make use of the backtracking pattern, so it'll be worth looking into in greater detail.
parents	approach_1_backtracking, intuition