回溯（Backtracking）、DFS（深度优先搜索）和枚举（Enumeration）之间的关系

枚举（最general的概念）
   ↓
DFS（特定的枚举实现方式）
   ↓
回溯（带"选择"和"撤销"的DFS）

DFS（深度优先搜索）

• 枚举的一种具体实现方式
• 按深度优先的顺序进行枚举

回溯（Backtracking）

• DFS的一种特殊形式
• 包含**”选择”和“撤销选择”**的过程
• 通常用于求解排列、组合等问题

回溯模板和浅拷贝问题

全排列问题：

正确代码：

class Solution:
    def permuteUnique(self , num: List[int]) -> List[List[int]]:
        results = []
        self._backtrace([],num,[False,]*len(num),results)
        return results
    @staticmethod
    def _backtrace(state:List[int],choices:List[int],selected:List[bool],res: List[List[int]]):
        """
        state: 已经选的元素组成的列表
        choices:所有可选元素，恒定为num
        selected:索引是否被选过的列表
        res:最终结果
        """
        # 不改变choices的元素，通过selected来记录是否选过元素
        if len(state)==len(choices):
            res.append(state.copy()) # 非常容易出错，不能是引用，或list(state)
            return
        for i,choice in enumerate(choices):
            if selected[i] ==False:
                state.append(choice)
                selected[i]=True
                Solution._backtrace(state,choices,selected,res)
                state.pop()
                selected[i]=False

错误代码：

class Solution:
    def permuteUnique(self , num: List[int]) -> List[List[int]]:
        results = []
        self._backtrace([],num,[False,]*len(num),results)
        return results
    @staticmethod
    def _backtrace(state:List[int],choices:List[int],selected:List[bool],res: List[List[int]]):
        """
        state: 已经选的元素组成的列表
        choices:所有可选元素，恒定为num
        selected:索引是否被选过的列表
        res:最终结果
        """
        # 不改变choices的元素，通过selected来记录是否选过元素
        if len(state)==len(choices):
            res.append(state) # 非常容易出错，不能浅拷贝
            return
        for i,choice in enumerate(choices):
            if selected[i] ==False:
                state.append(choice)
                selected[i]=True
                Solution._backtrace(state,choices,selected,res)
                state.pop()
                selected[i]=False