2020-04-22

针对39题，想起来，爬楼梯问题，分硬币问题。
想到了用 dfs 递归来解决。
1、针对不允许重复，想到了单调栈，这里也就是list
2、针对candidates ，进行排序，可以在循环时，break，加速
3、注意，剪枝。通过单调栈，进行剪枝。
4、注意，列表的引用传递。
5、硬币本身可以重复多次，但要的是组合，不是排序。

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        ans=[]
        c=candidates
        c.sort()
        def dfs(n,st):
            if n<0:return
            if n==0:
                ans.append(st)
                return

            #this level
            for i in c:
                if i>n:break
                if n >= i and (not st or i >= st[-1]): #用单调栈，sort 非必要。
                    dfs(n-i,st+[i])

        dfs(target,[])
        return ans

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        ans=[]
        c=candidates
        def dfs(n,st):
            if n<0:return
            if n==0:
                ans.append(st);return

            #this level
            for i in c:
                if n >= i and (not st or i >= st[-1]):
                    st.append(i)
                    dfs(n-i,st[:])  #这种写法能看出 回溯的影子。
                    st.pop()   #the most useful point
        dfs(target,[])
        return ans