LeetCode 39. Combination Sum

2 min readMay 15, 2020

https://leetcode.com/problems/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.

Note:

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:
[
  [7],
  [2,2,3]
]

Example 2:

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

Discuss

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

Solutions

DP

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%.

https://gist.github.com/coldmanck/89614fd33b0d4d0acc608a623d496cd6

BFS

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%.

https://gist.github.com/coldmanck/89614fd33b0d4d0acc608a623d496cd6

Backtrack

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%.

https://gist.github.com/coldmanck/7c9e40cd60632b73b9338967d80c7973

Reference

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