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