Using recursion, I'm getting an answer one less than the correct answer

Question

The question is:

Given an integer array with all positive numbers and no duplicates, find the number of possible combinations that add up to a positive integer target.

Example:
nums = [1, 2, 3]
target = 4
The possible combination ways are:
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)
Note that different sequences are counted as different combinations.

Therefore the output is 7.

def combinationSum4(nums: List[int], target: int) -> int:
    if target == 0:
        return 1
    elif target < 0:
        return 0
    elif len(nums) == 0:
        return 1
    else:
        return combinationSum4(nums[1:], target-nums[0]) + combinationSum4(nums[1:], target)

The output is 7 but I'm getting 6 instead.

this may help: https://stackoverflow.com/questions/10035752/elegant-python-code-for-integer-partitioning and this: https://en.wikipedia.org/wiki/Partition_%28number_theory%29 — hiro protagonist, Nov 07 '20 at 19:37
Why should the result for `target == 0` and `len(nums) == 0` be 1 and not 0? — mkrieger1, Nov 07 '20 at 19:41

score 1 · Answer 1 · answered Nov 07 '20 at 21:15

I'd like to introduce another approach to solve it by recursion, take a look at this:

m_nums = [1, 2, 3]
m_target = 4

def recursive_implementation(nums, target, cnt):
    if target == 0:
        return cnt+1
    else:
        for item in nums:
            if item<=target:
                cnt = recursive_implementation(nums, target-item, cnt)
    return cnt
                    

a = recursive_implementation(m_nums, m_target, 0)
print(a)

output:

for sanity check, I tried it also on the input - 1, 2 target: 4 options are:

(1,1,1,1)
(1,1,2)
(1,2,1)
(2,1,1)
(2,2)
# output of the recursion - 5

score 1 · Answer 2 · answered Nov 08 '20 at 04:01

I like @YossiLevi's general approach, but I would avoid his extra argument and simply do:

def combinationSum(numbers, target):
    if target == 0:
        return 1  # base case

    count = 0

    for number in numbers:
        if number <= target:
            count += combinationSum(numbers, target - number)

    return count

print(combinationSum([1, 2, 3], 4))

Using recursion, I'm getting an answer one less than the correct answer

2 Answers2