# Share My Python Solution beating 98.17%

• ``````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``````

• It's amazing that your solution is much faster than most of solutions! I will appreciate it if you could explain what's the actual meaning of your pruning ~..~, thanks

• Hello Boromir,

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

1. 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.

2. 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).

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 79ms

``````class 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

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.