Combination Sum

MediumBacktrackingcombination-sum

Given an array of distinct integers nums and a target integer target, return a list of all unique combinations of numbers from nums where the sum equals target.

Each number from nums may be used unlimited number of times. Two combinations are considered the same if the frequency of each number used in them matches.

The combinations in the answer may be returned in any order, and the numbers within each combination may also be in any order.

Example 1:

Input: nums = [2,5,6,9] target = 9 Output: [[2,2,5],[9]] Explanation: 2 + 2 + 5 = 9 (use 2 twice and 5 once) 9 = 9 (use 9 once)

Example 2:

Input: nums = [3,4,5] target = 16 Output: [[3,3,3,3,4],[3,3,5,5],[3,4,4,5],[4,4,4,4]]

Recommended complexity

The time complexity of the solution will be exponential O(n^target), where n is the size of the nums array, as we consider all possible combinations. Space complexity is O(target) for storing the current combination in recursion.


Hint 1

Think about using recursion. For each number, we have a choice: either include it in the current combination and continue searching with a reduced target, or skip it.


Hint 2

Use backtracking to build combinations. At each step, either take the current number and reduce the target by its value, or move to the next number.


Hint 3

To avoid duplicates in the answer, you can use the index of the current number and only allow taking numbers starting from this index. This ensures that we don't build the same combination twice.

Problem of finding all unique combinations of numbers that sum to a given target. Develops skills in working with recursion, backtracking, and combinatorics. Helps improve understanding of search algorithms with backtracking and processing tree-like data structures.
solution.js · saved

Input

[2,5,6,9], 9

Expected Output

[[2,2,5],[9]]