回溯算法章节小总结

回溯算法章节小总结

仅供自己忘了的时候看看

文章目录

• 回溯算法章节小总结
• • 1.树层去重
  • • 1.可以对原数组排序的
    • 2.原数组不可以排序的，可以用哈希表
  • 2.树枝去重
  • 3.区间切割
  • 4.棋盘问题

1.树层去重

1.可以对原数组排序的

40. 组合总和 II - 力扣（LeetCode）

通过排序+相邻元素相同+used数组来进行去重

		void backtracking(vector<int>& candidates, int target, int sum, int startIndex, vector<bool>& used) {
        if (sum == target) {
            result.push_back(path);
            return;
        }
        for (int i = startIndex; i < candidates.size() && sum + candidates[i] <= target; i++) {
            // used[i - 1] == true，说明同一树枝candidates[i - 1]使用过
            // used[i - 1] == false，说明同一树层candidates[i - 1]使用过
            // 要对同一树层使用过的元素进行跳过
            if (i > 0 && candidates[i] == candidates[i - 1] && used[i - 1] == false) {
                continue;
            }
            sum += candidates[i];
            path.push_back(candidates[i]);
            used[i] = true;
            backtracking(candidates, target, sum, i + 1, used); // 和39.组合总和的区别1，这里是i+1，每个数字在每个组合中只能使用一次
            used[i] = false;
            sum -= candidates[i];
            path.pop_back();
        }
    }

2.原数组不可以排序的，可以用哈希表

90. 子集 II - 力扣（LeetCode）（本题可以排序）

使用set哈希表来对同一层选过的元素进行标记

void backtracking(vector<int>& nums, int startIndex) {
        result.push_back(path);
        unordered_set<int> uset;
        for (int i = startIndex; i < nums.size(); i++) {
            if (uset.find(nums[i]) != uset.end()) {
                continue;
            }
            uset.insert(nums[i]);
            path.push_back(nums[i]);
            backtracking(nums, i + 1);
            path.pop_back();
        }
    }

2.树枝去重

1.一般是在参数index处去除，传入i+1就避免了这一问题

2.排序+used数组

47. 全排列 II - 力扣（LeetCode）

	vector<vector<int>> result;
    vector<int> path;
    void backtracking (vector<int>& nums, vector<bool>& used) {
        // 此时说明找到了一组
        if (path.size() == nums.size()) {
            result.push_back(path);
            return;
        }
        for (int i = 0; i < nums.size(); i++) {
            // used[i - 1] == true，说明同一树枝nums[i - 1]使用过
            // used[i - 1] == false，说明同一树层nums[i - 1]使用过
            // 如果同一树层nums[i - 1]使用过则直接跳过
            if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) {
                continue;
            }
            if (used[i] == false) {
                used[i] = true;
                path.push_back(nums[i]);
                backtracking(nums, used);
                path.pop_back();
                used[i] = false;
            }
        }
    }

3.区间切割

问题模板：

重点是理解区间[index,i]的使用

res结果集;
bool is([index,i]区间)
{
    //判断合法性
    return true or false;
}
void backtracking(函数参数)
{
    if(终止条件)
    {
        res结果收集;
	}
    for(int i=index;i<s.size();i++)
    {
        if(is(传入[index,i]这个区间))
            path收集;
        else
            break or continue;
        //下一层递归
        backtracking(函数参数);
        回溯过程;
    }
}

4.棋盘问题

37. 解数独 - 力扣（LeetCode）

二维的回溯，其实就是一维铺开，还是一维的思考方式，只不过遍历的时候遍历的是二维而已。