07-18：回溯法review

1、和为目标值的数组元素组合

def dfs(path,target,start):

            if target<0:

                return

            if target == 0:

                res.append(path[:])

                return

            for i in range(start,n):

                if i!=start and num[i] == num[i-1]:

                    continue

                dfs(path+[num[i]],target-num[i],i+1)

        res = []

        n = len(num)

        num.sort()

        dfs([],target,0)

        return res

https://www.nowcoder.com/practice/75e6cd5b85ab41c6a7c43359a74e869a?tpId=117&&tqId=37742&rp=1&ru=/activity/oj&qru=/ta/job-code-high/question-ranking

2、和为目标值的二叉树路径

ret = list()

        path = list()

        def dfs(root, target):

            if not root:

                return

            path.append(root.val)

            target -= root.val

            if not root.left and not root.right and target == 0:

                ret.append(path[:])

            dfs(root.left, target)

            dfs(root.right, target)

            path.pop() 

            #pop利用了栈的性质，注意的是：先进后出

        dfs(root, sum)

        return ret

https://www.nowcoder.com/practice/840dd2dc4fbd4b2199cd48f2dadf930a?tpId=117&&tqId=37718&rp=1&ru=/activity/oj&qru=/ta/job-code-high/question-ranking