Back to DSA

Combination Sum

medium
Acceptance: 51%
BacktrackingArrays

Given an array of distinct positive integers (candidates) and a target sum, find all unique combinations of candidates that add up to the target. Each candidate may be used an unlimited number of times. Two combinations are different if they differ in the frequency of at least one chosen number.

Examples

Example 1:
Input:candidates = [3,5,7], target = 10
Output:[[3,7],[5,5]]
Example 2:
Input:candidates = [2,4,6], target = 8
Output:[[2,2,2,2],[2,2,4],[2,6],[4,4]]

Hints

Related Problems

Remove Duplicates from Sorted ArrayeasyBest Time to Buy and Sell StockeasyTwo SumeasyMerge Sorted ArrayeasyMove Zeroeseasy
00:00
import java.util.*;

class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> result = new ArrayList<>();
        backtrack(candidates, target, 0, new ArrayList<>(), result);
        return result;
    }

    private void backtrack(int[] candidates, int remain, int start, List<Integer> current, List<List<Integer>> result) {
        if (remain == 0) { result.add(new ArrayList<>(current)); return; }
        for (int i = start; i < candidates.length; i++) {
            if (candidates[i] > remain) continue;
            current.add(candidates[i]);
            backtrack(candidates, remain - candidates[i], i, current, result);
            current.remove(current.size() - 1);
        }
    }
}
Time complexityO(n^(T/M))
Space complexityO(T/M)