LeetCode 39. Combination Sum

Description

https://leetcode.com/problems/combination-sum/description/

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

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

Note:

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

For example, given candidate set [2, 3, 6, 7] and target 7,
A solution set is:

Explanation

Combinations are similar to subsets of the candidate array. We can use depth-first search to find all combinations of the input array.

First, sort candidates array into ascending order.
Second, conduct a depth-first search to visit each combination of the input array.

A depth-first search function would be:
Whenever adding an element to the combination, we reduce the target.
If the remaining target value is equal to 0, we add the current combination to the result list.
Then, recursively find all combinations for the remaining target value from the remaining elements.

Video Tutorial

Java Solution

4 thoughts

  1. Hey GoodTecher! Thank you so much for the tutorials! They are awesome. Can you please do more DP problems, showing how to think and attack those problems?
    Also, please do Combination Sum IV.

  2. Hi Good Techer,

    Thank you so much for making this video in comparison with the previous one. They are very helpful.

    Looking forward to your next video.
    With all my thanks,

Leave a Reply

Your email address will not be published. Required fields are marked *