Backtracking/Combination SumMedium

This practice workspace is built for desktop. Open it on a larger screen to start solving.

Combination Sum

Backtracking·Medium

Given an array of distinct positive integers candidates and a target integer target, return a list of all unique combinations of candidates where the chosen numbers sum to target.

The same number may be chosen from candidates an unlimited number of times. Two combinations are unique iff the multiset of chosen numbers differs.

For deterministic comparison: sort each inner combination in ascending order and sort the outer list lexicographically (compare element-by-element; shorter prefix sorts before longer with the same prefix).

By convention, target = 0 yields the single empty combination: [[]].

Examples

Input: candidates = [2,3,6,7], target = 7

Output: [[2,2,3],[7]]

2+2+3 = 7 (2 reused). 7 = 7. No other combinations.

Input: candidates = [2,3,5], target = 8

Output: [[2,2,2,2],[2,3,3],[3,5]]

Input: candidates = [2], target = 1

Output: []

Constraints

1 <= candidates.length <= 30
2 <= candidates[i] <= 40
All elements of candidates are distinct.
1 <= target <= 40

00:00Preview Mode (Read Only)

Loading editor…

Tests

Preview Mode

This is a read-only preview of DSAMind's AI coaching. Sign up to get custom feedback on your own solution.

Passed32 ms

First attempt — retry to track metric movement here.

Your approach

Pattern:Backtracking
Time:O(N)
Space:O(1)

Complete approach — pattern and complexity both named.

Coach

What you got right

You correctly matched the sorted input requirement and implemented a linear-time scan using two pointers.

Where it diverged

No divergence detected. The code correctly aligns with the stated approach.

Next attempt: focus on

Try solving related sliding window problems to build familiarity with two-pointer variants.

Signals

No signals fired — clean run, you stayed in flow.