LeetCode 39. Combination Sum


Problem Description

Given a set of candidate numbers (candidates) (without duplicates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target.

The same repeated number may be chosen from candidates unlimited number of times.


  • All numbers (including target) will be positive integers.
  • The solution set must not contain duplicate combinations.

Example 1:

Input: candidates = [2,3,6,7], target = 7,
A solution set is:

Example 2:

Input: candidates = [2,3,5], target = 8,
A solution set is:


There are at least three kinds of concise solution to this problem. Namely, dynamic programming, breadth first search and backtracking.



Construct a 1d table for recording combinations in a bottom-up manner. Time O(mn) where m denotes the number of candidates and n is the target. Time beats ~88%.



Basic idea is similar to 279. Perfect Squares
For each element pop from the queue, and for each possible candidates, minus it from the current target. If the result equals zeros then we get a solution; if the result is greater than zero then we keep push it into the queue; if the result is smaller than zero than we just stop proceeding there. Time beats ~82%.



The idea is very similar to 77. Combinations but we need to record and pass cur_sum, and the base case is to check if cur_sum is equal to or larger than target. Time beats ~62%.



My solutions are also available here: https://leetcode.com/problems/combination-sum/discuss/632799/Three-Python-easy-solutions-(DPBFSBacktrack)-with-explanation.-Time-beats-~88



Computer Vision Applied Scientist @ Amazon. https://coldmanck.github.io

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store