[回溯算法] Backtrack

[Linjiayu6]

回溯问题 = 决策树遍历过程

1. 路径 做出选择
2. 选择列表 你可以做的选择
3. 结束条件 到达决策树底层 无法再做选择

[Linjiayu6]

1 - 46. 全排列

# 第一版
class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        _len = len(nums)
        if _len == 0: return []
        if _len == 1: return [nums]

        result = []
        def select(selectedlist, todolist): # 已经选择 / 待选择
            if len(todolist) == 0: # 可选择列表为空
                result.append(selectedlist) # 将值直接返回, 结束
                return

            for i in range(len(todolist)): # 遍历选择
                newselect = selectedlist + [todolist[i]] # 我做出的选择
                newtodo = todolist[0:i] + todolist[i+1:] # 新的待选择
                select(newselect, newtodo)

        select([], nums) # 初始化执行 已选择列表为空, 待选择为整个排序
        return result

leetcode 讲解

# 第二版
class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        _len = len(nums)
        if _len == 0: return []
        if _len == 1: return [nums]

        result = []
        def backtrack (pos, nums):
            if pos == _len:
                result.append(nums[:]) # 不能直接写nums,会返回值都一样的, 深拷贝
                return

            for i in range(pos, _len):
                nums[pos], nums[i] = nums[i], nums[pos] # 交换 选择
                backtrack(pos + 1, nums)
                nums[pos], nums[i] = nums[i], nums[pos] # 撤回 回溯

        backtrack(0, nums) # 是通过交换位置, 不用每次都创建新的todolist
        return result

同 面试题38. 字符串的排列 TODO

输入：s = "abc"
输出：["abc","acb","bac","bca","cab","cba"]