I'm working on LeetCode 40. Combination Sum II
Given a collection of candidate numbers (candidates) and a target number (target), find all unique combinations in candidates where the candidate numbers sum to target.
Each number in candidates may only be used once in the combination.
Note: The solution set must not contain duplicate combinations.
My code below works until the candidates collection gets too big, then I get back "time limit exceeded". All of the recursion is creating too many loops I think. I can obviously copy tutorials to get the answer but I'm trying to figure out how my code could be updated to work in order to understand better how recursion works.
class Solution:
def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
candidates.sort()
answers = []
strings = []
total = sum(candidates)
if total < target:
return []
def backtrack(total, array, index):
if total == 0:
string = ''
for each in array:
string += str(each)
if string not in strings:
answers.append(array)
strings.append(string)
return
if index >= len(candidates):
return
for each in range(index, len(candidates)):
backtrack(total - candidates[each], array + [candidates[each]], each + 1)
backtrack(total, array, each + 1)
backtrack(target, [], 0)
return answers
Some issues that are a hit to performance:
When total becomes negative, it is useless to continue the recursive process: it will only get more negative.
The second call to backtrack is implementing the same idea as the for loop. Consider that in the loop all possible values for each + 1 will be passed to backtrack(total, array, each + 1). But then also note that one level deeper in the recursion tree, all of these -- except the first -- are made again! So either remove backtrack(total, array, each + 1) or else keep it, and remove the for loop.
When two consecutive values are the same, and the recursive call has been made for the first of these two, it is useless to make a recursive call with the duplicate value. At that moment there is one fewer value to choose from, and the total is the same, so there cannot come any new combinations from that. So if we go for the for loop (see previous point), then only make recursive calls for distinct values (the first time they occur).
There is also this bug:
1, 2, 3 is stringified, it becomes "123". But also 1, 23 would be stringified like that, and this could lead to false negatives. So this is actually a bug in the code that goes undetected on LeetCode. You can solve this by using separator characters.Here is your code adapted with those points taken into account:
class Solution:
def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
candidates.sort()
answers = []
strings = []
total = sum(candidates)
if total < target:
return []
def backtrack(total, array, index):
if total == 0:
string = ''
for each in array:
string += "_" + str(each) # Separate the values
if string not in strings:
answers.append(array)
strings.append(string)
return
if index >= len(candidates) or total < 0: # give up when total becomes negative
return
current = -1
for each in range(index, len(candidates)):
if candidates[each] != current: # Avoid duplicates
current = candidates[each]
backtrack(total - current, array + [current], each + 1)
# Don't make another recursive call here. The for-loop is already skipping candidates
backtrack(target, [], 0)
return answers
There is still room for improvement. You could think of the following points:
Your code currently checks that the total is not greater than the overall sum. You could extend this, and verify that the total is not greater than the remaining sum, during the recursive process. You would prepare a list with all these "remaining" sums before starting the recursion, and then check the total against the relevant value in that list.
if string not in strings is not so efficient when strings is a list. It would be better to use a set for strings.
Instead of using strings as identifiers, you could create tuples instead of sub lists. These are hashable, so if you store them in an overall set instead of list, you will not get duplicates. Then at the very end you can convert that set of tuples to the final list of lists.