Problem Statement in English

You’re given a list of integers - nums. Your task is to return every possible unique combination of the elements that results in a sum equaivalent to target. You’re allowed to use any element as many times as you want.

For example, if you had nums = [2,3], targetSum = 6, then your answer would be [[2,2,2],[3,3]].

Approach

I’d recommend first checking out this post. We’re going to be building on top of the fundamental idea used there. With one major modification - instead of only using an element once, we can use it multiple times.

As you can probably imagine, this results in the generation of a massive number of possibilities.

The constraints give us an important optimisation to make. There are no negative elements in nums. This means that if we ever overshoot the target, we can discontinue further generation along that line.

Step 1: At every node, we have 2 possibilies, either using the current index again, or skipping it.

  • Step 1.1.1: If including the current index keeps us within the target:
    Include it. Make a new recusive call with the updated list (which now has the same index again).

  • Step 1.1.2: If including the current index gives us the target:
    Stop generating and add this combination to the answers.

  • Step 1.2: If including the next index is within range:
    Make a recursive call including the next index, and excluding the current one (otherwise we will cause a stackoverflow in the recusion stack (how I know? because guess who got a stackoverflow error, totally wasn’t me, ahem).

Solution in Python


class Solution:
    def combinationSum(self, nums: List[int], target: int) -> List[List[int]]:
        ans = []

        def recursiveCall(l: List, i: int, currentSum: int):
            # the index has gone out of range,
            # stop generating
            if i > len(nums) - 1:
                pass

            # once with this index - only if we're <= target
            elif currentSum + nums[i] <= target:
                yes = l.copy()
                yes.append(nums[i])

                # if it's lesser than target,
                # continue generating
                if currentSum + nums[i] < target:
                    recursiveCall(yes, i, currentSum + nums[i])
                
                # if it gives the target,
                # add to `ans`,
                # and stop generating
                else:
                    ans.append(yes)
            
            # if the index is still within range
            if i < len(nums):
                # once without this index
                no = l.copy()
                recursiveCall(no, i + 1, currentSum)

        # initial call to kick things off
        recursiveCall([], 0, 0)

        # return the final answer
        return ans
  • A significantly faster approach thanks to sorting the input list and breaking early when we overshoot the target:

class Solution:
    def combinationSum(self, nums: List[int], target: int) -> List[List[int]]:
        N = len(nums)
        
        nums.sort(reverse=True)
        res = []
        temp = []
        s = 0

        def solve(i):
            nonlocal s, temp, res

            if s == target:
                res.append(temp.copy())
                return

            if i >= N:
                return

            if s + nums[i] <= target:                
                temp.append(nums[i])
                s += nums[i]
                
                solve(i)

                temp.pop()
                s -= nums[i]

            solve(i + 1)

        solve(0)

        return res

Complexity

  • Time: $O(2^\frac{target}{min(nums)})$
    Since at every step we have 2 possibilities, and let’s say the height of the recursion tree is $h$, then the time complexity is $O(2^h)$.

    The height of the recursion tree is determined by the number of elements in nums and the target value.

    In the worst case, we can have a height of $\frac{target}{min(nums)}$, where min(nums) is the smallest element in nums.

    Therefore, the time complexity can be approximated as $O(2^{\frac{target}{min(nums)}})$.

  • Space: $O(\frac{target}{min(nums)} \times k)$
    The space complexity is determined by the maximum depth of the recursion stack, which is $O(h)$, where $h$ is the height of the recursion tree.

    In the worst case, this can be $O(\frac{target}{min(nums)})$.

    Additionally, we need to consider the space used to store the results. We assume there are $k$ unique combinations that sum up to the target.

    If each combination has a maximum length of $\frac{target}{min(nums)}$, then the space required to store all combinations is $O(k \times (\frac{target}{min(nums)}))$.

Mistakes I Made

I didn’t read the part where it said you can use a single element as many times as you want.

And we are done.