DT走过的路

三大核心要素

1. 路径 path：当前已经做出的选择
2. 选择列表 choices：当前可做的所有选项
3. 结束条件：path 满足要求，记录结果

通用代码模板

// 存放最终全部答案
const res = [];
function backtrack(path, choices) {
    // 1. 终止条件：满足要求，保存副本（关键！不能直接存path）
    if (满足条件) {
        res.push([...path]); 
        return;
    }
    // 2. 遍历所有可选分支
    for (let i = 0; i < choices.length; i++) {
        const cur = choices[i];
        // 剪枝：当前分支不符合，直接跳过，减少循环
        if (不合法) continue;
        
        // 做选择
        path.push(cur);
        // 递归进入下一层
        backtrack(path, 新的可选集合);
        // 撤销选择（回溯核心）
        path.pop();
    }
}
// 启动
backtrack([], 初始选择列表);
return res;

适用场景

1. 排列类：全排列、全排列去重
2. 组合类：组合、子集、子集去重
3. 分割类：分割回文串、单词拆分
4. 棋盘类：N 皇后、数独
5. 路径类：矩阵路径、迷宫搜索

有重复字符串的排列组合

示例 1：

 输入：S = "qqe"
 输出：["eqq","qeq","qqe"]

function pailie(){
    // 输入：S = "qqe"
    // 输出：["eqq","qeq","qqe"]
    const s = "qeq".split('').sort().join('');
    const res = [];
    const path = [];
    const used = new Array(s.length).fill(false);
    const backtrack = () => {
        // 1. 终止条件：满足要求，保存副本（关键！不能直接存path）
        if (path.length === s.length) {
            res.push(path.join('')); 
            return;
        }
        // 2. 遍历所有可选分支
        for (let i = 0; i < s.length; i++) {
            const cur = s[i];
            // // 剪枝：当前分支不符合，直接跳过，减少循环
            if (used[i]) continue;
            if(i>0 && s[i-1] === s[i] && !used[i-1]) continue;
            used[i] = true;
            // 做选择
            path.push(cur);
            // 递归进入下一层
            backtrack()
            // 撤销选择（回溯核心）
            path.pop();
            used[i] = false;
        }
    }
    // 启动
    backtrack();
    console.log(res,'res');
}

var permutation = function(S) {
    const needS = S.split("").sort().join("");
    const res= [];
    const aset = new Set();
    const used = new Array(S.length).fill(0);
    const path=[];
    const back=()=>{
        if(path.length===needS.length){
            if(aset.has(path.join(""))){
                return;
            }
            aset.add(path.join(""));
            res.push(path.join(""));
            return;
        }
        for(let i=0;i<needS.length;i++){
            if(used[i]) continue;
            path.push(needS[i])
            used[i] =1;
            back();
            path.pop();
            used[i] = 0;
        }

    }
    back();
    return res;
};

给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。

你可以按 任何顺序 返回答案。

示例 1：

输入：n = 4, k = 2
输出：
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

示例 2：

输入：n = 1, k = 1
输出：[[1]]

var combine = function(n, k) {

    const path = [];
    const res = [];
    
    const back=(start)=>{
        if(path.length===k){
            res.push([...path]);
            return;
        }
        for(let i=start;i<n;i++){
          path.push(i+1);
          back(i+1);
          path.pop(); 
        }        

    }
    back(0);
    //console.log(res,'res');
    return res;
};

区别

1. 传 start、i 从 start 开始、递归传 i+1 → 求【组合 / 子集】，不允许重复顺序，不回头选前面数字

2. i 永远从 0 开始、不传 start → 求【全排列】，可以重复调换顺序，每个位置都能重新选全部元素