'Subset Sum/ Combination sum2 solution not working for larger numbers?
I'm trying to use subset sum/combination sum 2 solution to solve a problem.
Currently, it works for smaller numbers and certain numbers in my list. But it doesnt work for all. In fact, when I put up larger numbers, the output I get is an empty list. I was wondering if any of you had a smiliar problem and a possible solution.
To give you an idea, with the code I currently have, if the input is the following:
trial_list = [1.5,2.5,3.7,4,4.3,5,5,5,3,10]
trial_list_target = 20.5
combinationSum2(trial_list, trial_list_target)
the output that I currently get is
[[1.5, 4, 5, 5, 5],
[1.5, 4, 5, 10],
[2.5, 3, 5, 5, 5],
[2.5, 3, 5, 10],
[2.5, 3.7, 4.3, 5, 5],
[2.5, 3.7, 4.3, 10]]
which is correct
And if I use this as an input:
trial_list2 = [10,15,20,20,25,30,15,87,10,7,100]
trial_list2_target = 107
combinationSum2(trial_list2, trial_list2_target)
The output is:
[[7, 10, 10, 15, 15, 20, 30],
[7, 10, 10, 15, 20, 20, 25],
[7, 10, 15, 20, 25, 30],
[7, 15, 15, 20, 20, 30],
[7, 100],
[10, 10, 87],
[20, 87]]
Again which is correct.
However, if I have the following list and target as an input:
trial_list3 = [806.0, 687.67, 590.9, 587.71, 561.88, 493.73, 427.16, 427.16, 412.04, 272.2, 262.82, 262.82, 86.15, 86.15, 86.15, 86.15, 86.15, 86.15, 3.0]
trial_list3_target = 959.87
combinationSum2(trial_list3, trial_list3_target)
The output I get is:
[]
Thats literally my output when it should be
[687.67,272.2].
please help, I'm literally struggling to get why this is happening
FYI, the argument for my function is passed through a pandas dataframe column. Thats the list I'm using as an argument.
This is the whole code I am using:
def combinationSum2(candidates, target):
# Sorting in earlier cell didnt work so sort here
candidates.sort()
result = []
combine_sum_2(candidates, 0, [], result, target)
return result
def combine_sum_2(nums, start, path, result, target):
# if sum greater than path, stop working
if not target:
result.append(path)
return
for i in range(start, len(nums)):
# Not sure what this does, copy paste stack overslow
if i > start and nums[i] == nums[i - 1]:
continue
# I think this is to limit search. i.e, if number > target then stop working
if nums[i] > target:
break
# We change the start to `i + 1` because one element only could
# be used once
combine_sum_2(nums, i + 1, path + [nums[i]],
result, target - nums[i])
Sources
This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.
Source: Stack Overflow
| Solution | Source |
|---|
