回溯算法

基本思路

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

题型

排列 组合 子集。
组合和子集是等价的。

剪枝

回溯法提升效率的关键是合理剪枝，有：

• 如果sum>target， 及时退出
• 需要回头时，维护used vector， 并有重复元素时，要通过设定顺序剪枝，如：

// 新添加的剪枝逻辑，固定相同的元素在排列中的相对位置
if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) {
    // 如果前面的相邻相等元素没有用过，则跳过
    continue;
}
// 选择 nums[i]

当出现重复元素时，比如输入 nums = [1,2,2',2'']，2' 只有在 2 已经被使用的情况下才会被选择，同理，2'' 只有在 2' 已经被使用的情况下才会被选择，这就保证了相同元素在排列中的相对位置保证固定。

元素的重复选择

从i开始选择。
backtrack（i，res)