Combination Sum

Problem

You are given an array of distinct integers nums and a target integer target. Your task is to return a list of all unique combinations of nums where the chosen numbers sum to target.

The same number may be chosen from nums an unlimited number of times. Two combinations are the same if the frequency of each of the chosen numbers is the same, otherwise they are different.

You may return the combinations in any order and the order of the numbers in each combination can be in any order.

Examples

Example 1:

Input:
nums = [2,5,6,9]
target = 9

Output: [[2,2,5],[9]]

Example 2:

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

Output: [[3,3,3,3,4],[3,3,5,5],[4,4,4,4],[3,4,4,5]]

Constraints

• All elements of nums are distinct.
• 1 <= nums.length <= 20
• 2 <= nums[i] <= 30
• 2 <= target <= 30

You should aim for a solution with O(2^{(t/m)}) time and O(t/m) space, where t is the given target and m is the minimum value in the given array.

Solution

Sorting the values first is O(n log n). This allows us to stop searching once we have a partial sum that goes over the target (since all elements to the right will also go over the sum).

We use DFS to create a search tree, where in recursion we search over the window from the idx_start to the end. The base case is that we found the target, and can add to our result.

class Solution {
public:
    vector<vector<int>> combinationSum(vector<int>& nums, int target) {
        // Sort the nums
        std::sort(nums.begin(), nums.end());
 
        std::vector<std::vector<int>> result;
        std::function<void(std::size_t, std::vector<int>, int)> runner;
        runner = [&](std::size_t idx_start, std::vector<int> curr_list, int curr_sum) {
            // If curr_list matches target, record this sum
            if (curr_sum == target) {
                result.push_back(curr_list);
                return;
            }
            // Otherwise, we can try all numbers from idx_start to end 
            //   (including idx_start again)
            for (std::size_t i = idx_start; i < nums.size(); ++i) {
                // If this sum goes over the target, stop
                if (curr_sum + nums[i] > target) {
                    return;
                }
                // Otherwise, add to current list and check for another 
                curr_list.push_back(nums[i]);
                runner(i, curr_list, curr_sum + nums[i]);
                curr_list.pop_back();
            }
        };
        runner(0, {}, 0);
        return result;
    }
};