Combination Sum
Explore how to identify all unique combinations of numbers that sum to a specific target using dynamic programming. Learn to apply techniques like memoization and tabulation to solve combination sum problems efficiently. This lesson helps you build reusable strategies for complex problem solving in coding interviews.
We'll cover the following...
Statement
Given an array of distinct integers, nums, and an integer, target, return a list of all unique combinations of nums where the chosen numbers sum up to the target. The combinations may be returned in any order.
An integer from nums may be chosen an unlimited number of times. Two combinations are unique if the
frequency of at least one of the chosen integers is different.
Constraints:
-
nums.length -
nums[i] -
target - All integers of
numsare unique.
Examples
Understand the problem
Let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:
Combination Sum
Given the following array and target value, what will be the answer?
nums = [3, 6, 7]
target = 10
result = [[3, 7]]
result = [[3, 6], [3, 3, 3]]
result = []
result = [[7], [3, 6]]
Figure it out!
We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.
Try it yourself
Implement your solution in the following coding playground.
import java.util.*;public class CombinationSum {public static List<List<Integer>> combinationSum(int[] nums, int target) {// Replace this placeholder return statement with your codereturn new ArrayList<>();}}