class Solution(object):
def combinationSum(self, candidates, target):
result = []
candidates = sorted(candidates)
def dfs(remain, stack):
if remain == 0:
result.append(stack)
return
for item in candidates:
if item > remain: break
if stack and item < stack[1]: continue
else:
dfs(remain  item, stack + [item])
dfs(target, [])
return result
Share My Python Solution beating 98.17%


Hello Boromir,
Thank you for your response. I will try my best to explain my algorithm.

First, I sort the candidates list. So, in the for loop, if one item in candidates in bigger than "remain" the remaining items must bigger than remain. That's why I just break the for loop.

The second "if" in the for loop is for the purpose of avoiding duplicate terms and maintaining the answer in increasing order. We implement this purpose by avoiding appending items that is smaller than the last term in stack (if the stack is not empty).
That's how I pruning. Hope I answer your question.
Thank you!!


combined with other people's great solutions (the top voted C++ solution), which passes down the current index of the for loop, so that we can skip the used items and don't have to check if
item < stack[1]
. The improved version beats 99.04% in 79msclass Solution(object): def combinationSum(self, candidates, target): """ :type candidates: List[int] :type target: int :rtype: List[List[int]] """ def dfs(remain, combo, index): if remain == 0: result.append(combo) return for i in range(index, len(candy)): if candy[i] > remain: # exceeded the sum with candidate[i] break #the for loop dfs(remain  candy[i], combo + [candy[i]], i) candy = sorted(candidates) result = [] dfs(target, [], 0) return result

@ian34 why is it so fast? combo + [candy[i]] copies the tmp list for every DFS call, right? I though it would be much slower than using a shared list by calling append/pop functions