遍歷所有的組合方式

• 簡介
  • 經(jīng)典的數(shù)學(xué)組合問題，對應(yīng)之前的排列問題。
• 問題描述
  • 現(xiàn)在有四本書為A，B，C，D，要求選出兩本，輸出所有的選擇情況。
• 問題分析
  • 和之前一樣，如果試求組合數(shù)目，那么DP將會是一個(gè)不錯(cuò)的選擇，但是DP不是很擅長這種序列輸出的題。
  • 其實(shí)，這還是個(gè)回溯題，因?yàn)槊恳徊降膯栴}都是一樣的只不過參數(shù)不一樣罷了。
    • 每一步都是在剩余書籍中挑出一本。
    • 與之前的排列問題不同之處在于選過的書本不可以選了，也就是選了AB，B后面的選擇就沒有A了。
  • 實(shí)現(xiàn)與排列類似
• 代碼
  • # -*-coding:utf-8-*-# -*-coding:utf-8-*-result = []def solve(array, number, solution):global resultif len(solution) == number:# 表示所有書都分配完畢，輸出答案result.append(solution)returnfor i in range(len(array)):new_solution = solution + [array[i]]new_array = array[i+1:]solve(new_array, number, new_solution)if __name__ == '__main__':input = ['A', 'B', 'C', 'D']solve(input, 2, [])for item in result:print(item)print("共{}種組合".format(len(result)))
• 運(yùn)行結(jié)果
• 補(bǔ)充說明
  • 具體代碼可以查看我的Github，歡迎Star或者Fork
  • 參考書《你也能看得懂的Python算法書》
  • 書中錯(cuò)誤已經(jīng)修改

總結(jié)

以上是生活随笔為你收集整理的回溯算法-02遍历所有组合方式问题的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。