回溯算法|DFS刷题合集

46. 全排列

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var permute = function(nums) {
    let track=[];
    let res=[];
    const backtrack=(nums,track)=>{
        //判断终止条件
        if(nums.length==track.length){
            let newarr=[];
            track.forEach((item)=>{
    //踩坑点，如果直接push（track）的话是浅拷贝，最终的res全是空数组，都指向同一个track地址
                newarr.push(item);
            })
            res.push(newarr);//也可以直接concat来进行深拷贝
            return ;
        }
        for(let i=0;i<nums.length;i++){
            if(track.includes(nums[i])){
                continue;
            }
            //做选择，跳过已有的元素
    
            track.push(nums[i]);
            backtrack(nums,track);
            //取消选择
            track.pop();
        }
    }
    backtrack(nums,track);
    return res;
};

注意踩坑点：res.push(track)的话最终res返回的是[[],[],[],[]]，因为是浅拷贝，指向的都是同一个数组track的地址，而track回溯完之后即为空数组。

或者直接res.push([].concat(track));也可以

下面的组合/子集问题使用start变量保证元素nums[start]之后只会出现nums[start+1..]中的元素，通过固定元素的相对位置保证不出现重复的子集。

78. 子集

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var subsets = function(nums) {
    let res=[];
    let track=[];
    const backtrack=(nums,start)=>{
        res.push([].concat(track));

        for(let i=start;i<nums.length;i++){//用start来防止重复遍历,即保证数组之间的相对顺序
            track.push(nums[i]);
            backtrack(nums,i+1);
            track.pop();//回溯
        }
    }
    backtrack(nums,0);
    return res;

};

77. 组合

/**
 * @param {number} n
 * @param {number} k
 * @return {number[][]}
 */
var combine = function(n, k) {
    let res=[];
    let track=[];
    const backtrack=(nums,start)=>{
        if(track.length===k){
            res.push([].concat(track));
            return;
        }
        

        for(let i=start;i<=nums;i++){//用start来防止重复遍历,即保证数组之间的相对顺序
            track.push(i);
            backtrack(nums,i+1);
            track.pop();//回溯
        }
    }
    backtrack(n,1);
    return res;    
};

90. 子集 II

/**
 * @param {number[]} nums
 * @return {number[][]}
 */

 //重点在剪枝，把重复的剪掉
var subsetsWithDup = function(nums) {
    let track=[];
    let res=[];
    nums.sort();//先排序
    const backtrack=(nums,start)=>{
        res.push([].concat(track))

        for(let i=start;i<nums.length;i++){
            //如果相等则跳过，避免重复，结合具体例子理解
            if(i>start&&nums[i]===nums[i-1]) continue;//重点！！ i>start则说明在同一层的相同的剪掉(避免剪到下一层)，
            track.push(nums[i]);
            backtrack(nums,i+1);//深度遍历
            //取消选择
            track.pop();
        }
    }
    backtrack(nums,0);
    return res;
};

子集和组合差不多。

40. 组合总和 II

/**
 * @param {number[]} candidates
 * @param {number} target
 * @return {number[][]}
 */
var combinationSum2 = function(candidates, target) {
    let res=[];
    let track=[];
    let tracksum=0;
    candidates.sort();
    const backtrack=(nums,start,sum)=>{
        //判断
        if(tracksum===sum) {
            res.push([].concat(track));
            return;
        }

        if(tracksum>sum) return;


        for(let i=start;i<nums.length;i++){
            //剪枝
            if(nums[i]==nums[i-1]&&i>start)//只排除同一层
            continue;
            track.push(nums[i]);
            tracksum+=nums[i];//和与track同步
            backtrack(nums,i+1,sum);
            track.pop();
            tracksum-=nums[i];
        }
    }
    backtrack(candidates,0,target)
    return res;


};

47. 全排列 II

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var permuteUnique = function(nums) {
    let res=[];
    let track=[];
    let used=new Array(nums.length).fill(0);
    nums.sort();
    const backtrack=(nums)=>{
        if(nums.length==track.length){
            res.push([].concat(track));
        }
        for(let i=0;i<nums.length;i++){
            if(used[i]) continue;//跳过已经排序过的元素
            //剪枝逻辑
            if(!used[i-1] && nums[i]===nums[i-1] ) continue;//重点！ 确保跳过同一层的重复元素i（即i-1为0且nums[i]==nums[i-1]），若不是同一层的话i-1的值为1
            track.push(nums[i]);
            used[i]=1;
            backtrack(nums);
            track.pop();
            used[i]=0;

        }
    }
    backtrack(nums);
    return res;
};

对比一下之前的标准全排列解法代码，这段解法代码只有两处不同：

1、对nums进行了排序。

2、添加了一句额外的剪枝逻辑。

39. 组合总和

/**
 * @param {number[]} candidates
 * @param {number} target
 * @return {number[][]}
 */
var combinationSum = function(candidates, target) {
    let res=[];
    let track=[];
    let tracksum=0;
    const backtrack=(nums,start,target)=>{
        if(tracksum===target){
            res.push([].concat(track));
            return;
        }
        if(tracksum>target) return;

        for(let i=start;i<nums.length;i++){

            track.push(nums[i]);
            tracksum+=nums[i];
            backtrack(nums,i,target);//重点！ start不是i+1，题目要求元素可重复被选取
            track.pop();
            tracksum-=nums[i];
        }
    }

    backtrack(candidates,0,target);
    return res;

};

剑指 Offer II 080. 含有 k 个元素的组合

/**
 * @param {number} n
 * @param {number} k
 * @return {number[][]}
 */
var combine = function(n, k) {
    let res=[];
    let track=[];
    const backtrack=(n,start,k)=>{
        //判断
        if(track.length===k) {
            res.push([].concat(track));
            return;
        }
 
        for(let i=start;i<=n;i++){
            track.push(i);
            backtrack(n,i+1,k);
            track.pop();
        }
    }
    backtrack(n,1,k)
    return res;
};

216. 组合总和 III

/**
 * @param {number} k
 * @param {number} n
 * @return {number[][]}
 */
const combinationSum3 = function(k, n) {
    const res=[];
    const backtrack=(start,tracksum,track)=>{
        
        if(track.length==k){
            if(tracksum==n) {res.push(track.concat());}
            return;
        }


        for(let i=start;i<=9;i++){
            if(tracksum+i>n) break;
            track.push(i);

            backtrack(i+1,tracksum+i,track);
            track.pop();
 
        }

   
    }
    backtrack(1,0,[]);
    return res;

};

总结：

什么时候使用 used 数组，什么时候使用 start 变量
有些朋友可能会疑惑什么时候使用 used 数组，什么时候使用start变量。这里为大家简单总结一下：

排列问题，讲究顺序（即 [2, 2, 3] 与 [2, 3, 2] 视为不同列表时），需要记录哪些数字已经使用过，此时用 used 数组；
组合问题，不讲究顺序（即 [2, 2, 3] 与 [2, 3, 2] 视为相同列表时），需要按照某种顺序搜索，此时使用 begin 变量。

子集问题和组合问题本质上是一样的，无非就是 base case 有一些区别，所以把这两个问题放在一起看。

形式一、元素无重不可复选，即nums中的元素都是唯一的，每个元素最多只能被使用一次，backtrack核心代码如下：

/* 组合/子集问题回溯算法框架 */
void backtrack(int[] nums, int start) {
    // 回溯算法标准框架
    for (int i = start; i < nums.length; i++) {
        // 做选择
        track.addLast(nums[i]);
        // 注意参数
        backtrack(nums, i + 1);
        // 撤销选择
        track.removeLast();
    }
}

/* 排列问题回溯算法框架 */
void backtrack(int[] nums) {
    for (int i = 0; i < nums.length; i++) {
        // 剪枝逻辑
        if (used[i]) {
            continue;
        }
        // 做选择
        used[i] = true;
        track.addLast(nums[i]);

        backtrack(nums);
        // 取消选择
        track.removeLast();
        used[i] = false;
    }
}

Javascript版
/* 组合/子集问题回溯算法框架 */
const backtrack=(nums,start)=>{
        res.push([].concat(track))

        for(let i=start;i<nums.length;i++){
            //如果相等则跳过，避免重复，结合具体例子理解
            if(i>start&&nums[i]===nums[i-1]) continue;//重点！！ i>start则说明在同一层的相同的剪掉(避免剪到下一层)，
            track.push(nums[i]);
            backtrack(nums,i+1);//深度遍历
            //取消选择
            track.pop();
        }
    }


/* 排列问题回溯算法框架 */
    const backtrack=(nums)=>{
        if(nums.length==track.length){
            res.push([].concat(track));
        }
        for(let i=0;i<nums.length;i++){
            if(used[i]) continue;//跳过已经排序过的元素
            //剪枝逻辑
            if(!used[i-1] && nums[i]===nums[i-1] ) continue;//重点！ 确保跳过同一层的重复元素i（即i-1为0且nums[i]==nums[i-1]），若不是同一层的话i-1的值为1
            track.push(nums[i]);
            used[i]=1;
            backtrack(nums);
            track.pop();
            used[i]=0;

        }
    }

形式二：

nums中的元素可以存在重复，每个元素最多只能被使用一次，其关键在于排序和剪枝。如[2，3，3`]会重复[2,3] [2,3`]，要进行剪枝