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

--

--

--

A computer science Ph.D. candidate at National University of Singapore. https://coldmanck.github.io

Love podcasts or audiobooks? Learn on the go with our new app.

Recommended from Medium

Wordpress and SQL pod on the top of K8S using ansible.

How WWII Tanks Can Teach You Bioinformatics

Interviews now suck, thanks SkaeHub.

30 Days Coding Challenge — Day 9

A Guide to run the OIDC Conformance Suite with WSO2 Identity Server

Easily add a Lottie animation into your IOS project.

Software Desgin Patterns

Project and Team Management in Digital Era

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
Meng-Jiun Chiou

Meng-Jiun Chiou

A computer science Ph.D. candidate at National University of Singapore. https://coldmanck.github.io

More from Medium

Meta Interview Question Leetcode 121

LeetCode Patterns Adventure 20— Average of Levels in Binary Tree

LeetCode 206 — Reverse Linked List

733. Flood Fill