39. Combination Sum

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

Complexity

• Time: $O(?)$
  I’m not sure how viable it is to estimate this, and honestly, I’m not even sure how to. It’s very exponential. There’s a good reason behind why they cap the input size at 30.

• Space: $O(?)$
  Likewise.

Note: I looked online and I found a lot of conflicting answers for the time and space complexity of this problem.

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.