python 回溯初级练习代码

            
              #回溯练习
#给你两个整数 n和k，从1-n中选择k个数字的组合。比如n=4，那么从1,2,3,4中选取两个数字的组合，包括图上所述的四种[1, 2], [1, 3], [2, 3], [2, 4]。

def combine(n, k):
    #global res_list
    res_list = []
    def backtrack(n, k, start, list_one):
        if k == 0:
            res_list.append(list_one[:])#注意，这里必须要[:]，为什么，不然都是记录引用，每次List_one改变。他的内容也是改变之后的内容？
            #print(res_list)
            print(list_one)
            #return list_one
        else:
            for i in range(start, n+1):
                list_one.append(i)
                backtrack(n, k-1, i+1, list_one)
                list_one.pop()
    
    list_one = []
    backtrack(n , k, 1, list_one)
    print(res_list)

def combinationSum(candidates, target):
    '''
    找到数组中之和为target的所有组合
    '''
    def backtrack(candidates, remian, list_one, start):
        #退出条件是剩余值为0和为负
        if remian < 0:
            return
        if remian == 0:
            result_list.append(list_one[:])
            print(list_one)
            #print(result_list)
        else:
            for i in range(start, len(candidates)):
                
                remian = remian-candidates[i]
                if remian < 0:
                    break
                list_one.append(candidates[i])
                backtrack(candidates, remian, list_one, i)
                list_one.pop()
                #千万注意也要把remian加回来
                remian += candidates[i]


    result_list = []
    list_one = []
    candidates.sort()
    backtrack(candidates, target, list_one, 0)
    return result_list

combinationSum([2, 3, 6, 7], 7)