因为回溯需“试探—撤回”,swap后不还原会导致后续分支基于错误状态,造成漏解或重复;组合要求单向推进起点避免顺序影响,排列则通过swap在当前层任意交换;含重元素时须排序+同层剪枝。

递归回溯生成全排列时,为什么 swap 操作后必须还原?
因为回溯的本质是“试探—撤回”,不还原会导致后续分支看到错误的中间状态。比如对 [1,2,3] 递归到第 2 层交换了 nums[1] 和 nums[2],若不 swap 回来,下一次循环会基于已破坏的顺序继续,结果漏解或重复。
实操建议:
立即学习“C++免费学习笔记(深入)”;
- 每次
swap(nums[i], nums[start])后,递归调用backtrack(nums, start + 1) - 递归返回后立刻再执行一次
swap(nums[i], nums[start])撤销 - 切忌只在递归前 swap、忘了还原;也别用临时拷贝数组代替 swap(性能差且掩盖逻辑)
生成组合(如 C(n,k))和全排列的关键区别在哪?
组合不关心顺序,所以递归时起点要“单向推进”;而排列允许任意位置交换,起点始终是当前层 start。这是最常混淆的点。
实操建议:
立即学习“C++免费学习笔记(深入)”;
- 组合:递归参数用
backtrack(nums, start, path),每次从start开始枚举,下一层传i + 1(避免重复选前面的数) - 排列:用
backtrack(nums, start),每次从start到末尾枚举,靠swap控制可选位置 - 若误把组合写成从 0 开始枚举,会得到重复组合(如 [1,2] 和 [2,1] 都出现)
如何避免排列中重复元素导致的重复解?
当输入含重复数字(如 [1,1,2]),单纯 swap 会生成重复排列。核心不是去重结果,而是在搜索过程中剪枝。
实操建议:
立即学习“C++免费学习笔记(深入)”;
- 先对
nums排序:sort(nums.begin(), nums.end()) - 在 for 循环内加判断:
if (i > start && nums[i] == nums[i-1]) continue; - 注意条件必须是
i > start,而非i > 0——否则同一层首个重复元素也被跳过 - 这个剪枝依赖排序,且只对“同一层”的重复有效;不同层的相同值(如两个 1 在不同深度)是合法的
C++ 中用 vector 还是 string 实现更稳妥?
两者都行,但 vector 更通用、语义清晰;string 仅适合字符场景,且 swap 对 string 是常数时间(C++11 起),而 vector 的 swap 也是 O(1),无需担心性能。
实操建议:
立即学习“C++免费学习笔记(深入)”;
- 数值型问题(如整数排列)坚决用
vector<int></int>,避免字符转义、ASCII 计算等隐式转换陷阱 - 字符串排列可用
string,但注意s[i]是char,比较时别写成s[i] == '1'却传入数字 1 - 所有路径记录统一用
vector<int></int>或vector<string></string>,别混用string和vector<char></char>


















