#回溯練習
#給你兩個整數 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)
            
          

?