LeetCode 39. Combination Sum



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.


  • 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:

  [2, 2, 3]


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

class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> results = new ArrayList<>();
        if (candidates == null || candidates.length == 0) {
            return results;
        List<Integer> combination = new ArrayList<>();
        toFindCombinationsToTarget(results, combination, candidates, target, 0);
        return results;
    private void toFindCombinationsToTarget(List<List<Integer>> results, List<Integer> combination, int[] candidates, int target, int startIndex) {
        if (target == 0) {
            results.add(new ArrayList<>(combination));
        for (int i = startIndex; i < candidates.length; i++) {
            if (candidates[i] > target) {
            toFindCombinationsToTarget(results, combination, candidates, target - candidates[i], i);
            combination.remove(combination.size() - 1);

4 Thoughts to “LeetCode 39. Combination Sum”

  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 *