Search⌘ K
AI Features
Home
Courses
Grokking the Coding Interview Patterns in Python

Combination Sum

Explore how to find all unique combinations of numbers that add up to a target using dynamic programming. Learn to implement solutions allowing repeated use of elements while understanding constraints and optimization techniques.

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:

  • 1≤1 \leq nums.length ≤30\leq 30
  • 2≤2 \leq nums[i] ≤40\leq 40
  • 1≤1 \leq target ≤40\leq 40
  • All integers of nums are 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

1.

Given the following array and target value, what will be the answer?

nums = [3, 6, 7]

target = 10

A.

result = [[3, 7]]

B.

result = [[3, 6], [3, 3, 3]]

C.

result = []

D.

result = [[7], [3, 6]]

1 / 4

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.

Sequence - Vertical
Drag and drop the cards to rearrange them in the correct sequence.
1
2
3
4

Try it yourself

Implement your solution in the following coding playground.

Python
usercode > main.py
def combination_sum(nums, target):

    

    # Replace this placeholder return statement with your code

    return []
Combination Sum