算法模版速查

动态规划：

 

 

回溯：

框架：

result = []
def backtrack(路径, 选择列表):
    if 满足结束条件:
        result.add(路径)
        return

    for 选择 in 选择列表:
        做选择
        backtrack(路径, 选择列表)
        撤销选择

 

for 选择 in 选择列表:
    # 做选择
    将该选择从选择列表移除
    路径.add(选择)
    backtrack(路径, 选择列表)
    # 撤销选择
    路径.remove(选择)
    将该选择再加入选择列表

 

栗子：

class Solution:
    def __init__(self):
        self.res = []
    def permute(self, nums):
        self.backTrack(nums, [])
        return self.res

    def backTrack(self, nums, track):
        if len(nums) == len(track):
            self.res.append(track[:])
            return
        for i in nums:
            if i in track:
                continue
            track.append(i)
            self.backTrack(nums, track)
            track.remove(i)