# LeetCode 39. Combination Sum

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